Is it possible you remembered the specific details wrong or misinterpreted the question?
In your description, element $a$ in position $b$ is restricted to $a-b \ne \pm M$.
But if they just meant the difference was restricted: $a-b \ne M$,
Then the problem appears tractable.
I worked out that simpler problem, and I tried to generalize in a way that I hoped might give some freedom in working out the larger problem. But this just clarified for me why a recursive approach is very unlikely to work, which I discuss at the end.
Consider the function $f(N,M,P)$ which gives the number of permutations of a list of elements labeled 1 to $N$, where the element $a$ in position $b$ (first position is 1) satisfies $a-b \ne M$, and $b-a \ne P$.
To visualize this, separating it into two constraints allows $M$ and $P$ to shift those restrictions around separately.
1 2 3 4 5 M=0, restricted values for each position
. . . . . (positions in list)
1 2 3 4 5 P=0, restricted values for each position
3 4 5 M=2, restricted values for each position
. . . . . (positions in list)
1 2 3 4 P=1, restricted values for each position
For convenience, when $P \ge N$ so that it doesn't place restrictions on the permutations, define $g(N,M) = f(N,M,P)$. Similarly, $g(N,P) = f(N,M,P)$ when $M \ge N$ so that it places no restriction on the permutations.
In the special case $M=P=0$ the constraint from $M$ and $P$ are equivalent, so one can be ignored, allowing us to write $f$ in terms of $g$:
$$ f(N,0,0) = g(N,0). $$
From the symmetry of the problem:
$$ f(N,M,P) = f(N,P,M) $$
Let's first solve for $g(N,M)$, and then tackle the more general $f(N,M,P)$.
For $M=0$, each element has one placement restriction (and the restrictions are distinct). So choosing some element $i$, we will place it in some position $j$. There are $N-1$ different possibilities for the choice of $j$.
This selection removed the restricted position for element $j$, while the other $(N-2)$ elements still have one restriction. We can break the placement of $j$ into two options:
Place in $i$. This leaves all other elements with one restriction, so the remaining placement problem is now reduced to $g(N-2,0)$.
Place in a position $\ne i$. This now gives one placement restriction for $j$, and so each element has one restriction, and the remaining placement problem is reduced to $g(N-1,0)$
So this gives the recursive formula:
$$g(N,0) = (N-1) \left[ g(N-2,0) + g(N-1,0) \right] $$
And by looking at the simple situations by hand, can get the base cases.
$$g(1,0) = 0, \ \ g(2,0) = 1$$
This is the usual derangement recursive formula.
While I can't imagine someone coming up with this on the spot, it also turns out there is a closed form solution for this (see the derangement wiki article for details).
$$ g(N,0) = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor $$
For $M \ge N$, there is no restriction on any of the placements:
$$(M \ge N) \implies g(N,M) = N! $$
With $0<M<N$, the first $M$ elements will have no restrictions and the remaining elements will have one placement restriction. It terms of the positions, the last $M$ positions will allow all numbers.
For the last position, select an element $i$. There are two possibilities for what the remaining placement looks like:
If $i<M$, then $i$ had no placement restrictions, so using $i$ does not change the restrictions on any position. We have also removed one position with no restriction, so the remaining placement looks like $g(N-1,M-1)$.
If $i>=M$, then $i$ had a placement restriction, and we removed one position with no restriction. Because $i$ is placed, the position it was restricted from now can accept any of the remaining numbers. So the remaining placement looks like $g(N-1,M)$.
So this gives the recursive formula:
$$(0<M<N) \implies g(N,M) = (M-1) g(N-1,M-1) + (N-M+1) g(N-1,M) $$
This finishes the recursive solution for $g$.
When $M+P \ge N$, the first $N-M$ positions have a single number restriction on them, the last $N-P$ positions have a single number restriction on them, and the middle $M+P-N$ positions have no restrictions. This is just like the $g(N,M+P-N)$ case.
$$(M+P)\ge N \implies f(N,M,P) = g(N,M+P-N)$$
We have handled all cases currently except $0<M<N$ and $0<P<N$ such that $M+P<N$. This is where some elements have multiple restrictions. Because of the symmetry in $f$, we can consider $0<M\le P<N$ without loss of generality.
The first $P$ positions will have a single restriction, then $N-M-P$ positions with two restrictions, then the last $M$ positions have a single restriction.
Looking at the elements, the first $M$ elements will have a single restriction, then $N-M-P$ elements have two restrictions, then the last $P$ elements have a single restriction.
However this is where we must end. As there is no way forward with this method.
I separated the two constraints because I could see that placing a number in a selected position could unbalance how many single constrained positions there were for the "+" constraint and the "-" constraint of $a-b \ne \pm M$.
But in the more general problem, removing a position by placing a number in it, does not always result in a subproblem that is described with $f(N,M,P)$.
To visualize these constraints on the permutation, consider a directed graph with $2N$ nodes, one set of $N$ labeled $\{A_1,A_2,...,A_N\}$ and another labelled $\{B_1,B_2,...,B_N\}$. A directed edge $(A_i,B_j)$ exists if $i - j = M$, and directed edge $(B_j,A_i)$ exists if $j - i = M$ and $M \ne 0$.
The set of $A$ nodes can be considered the numbers we are permuting in some list, and $B$ nodes their possible positions. This graph represents the constraints. There will be no cycles in the graph. It will always be disjoint nodes or chains of length one or more.
So we want a function which takes as input this constraint graph, and outputs the number of permutations that satisfy the constraints.
In the case where $M+P\ge N$, the graph is just disjoint nodes and single edges. So removing an A and B node will give a subgraph that is also disjoint nodes and single edges.
However for $0<M \le P<N$, the graph can have long chains. To place a number in an available position, regardless of whether we fix the node or the position, we need to consider all the subgraphs of possible ways to build that. All the different ways of breaking up the chains will result in a "recursion" that is on the order of $N$ parts each round, and thus can't expect much if any savings compared to checking all $N!$ permutations.
Because there are so many possible subgraphs once chains are allowed, I really don't see how this can be solved with the usual recursive methods unless there is a clever relation saying how non-isomorphic constraint graphs are somehow equivalent for the number of permutations.
I think most likely, the question was misinterpreted. Possibly even by the interviewer (who may have forgotten the answer details themselves).
