# Recursion limit reached in a list of recursive functions

Here is a fragment of the code I was working on the other day, that is constructed from a recursive function with Memorization, whose input is prepared in a For loop and then modified as a boundary condition (depending on what I want).

n = 5; (*number of cycles/steps*)
For[i = -n - 1, i <= n + 1, i++,
f[i, 0] = {{0}, {0}}]
f[0, 0] = {{1}, {0}};
f[x_, t_] :=
f[x, t] =
N[{1/Sqrt[2] {1, 1}.f[x - 1, t - 1],
1/Sqrt[2] {1, -1}.f[x + 1, t - 1]}];
l = Table[f[i, n], {i, -n, n}]


The resulting list l does have values that are correct, but everything works only up to n=3, for a larger n I get "$RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation of...". My natural reaction was to increase Recursion limit using $RecursionLimit=12000


but it didn't help, and for values of 20000 and larger the code just stops working without any error or beep. What am I doing wrong?

You make a call outside of the range bounded by your termination conditions. E.g. f[5,1] calls f[6,0] and then hell breaks lose. You can fix that by extending your For loop by several steps to the left and to the right.

You can even skip the whole loop if you use the following:

ClearAll[f]
n = 5;
f[n_, 0] = {{0.}, {0.}};
f[0, 0] = {{1.}, {0.}};
q = 1./Sqrt[2.];
f[x_, t_] := f[x, t] = {{q, q}.f[x - 1, t - 1], {q, -q}.f[x + 1, t - 1]};
l = Table[f[i, n], {i, -n, n}]


{{{0.}, {0.176777}}, {{0.}, {0.}}, {{-0.176777}, {0.353553}}, {{0.}, {0.}}, {{0.}, {-0.353553}}, {{0.}, {0.}}, {{0.}, {0.353553}}, {{0.}, {0.}}, {{0.707107}, {0.176777}}, {{0.}, {0.}}, {{0.176777}, {0.}}}

• Yep, that works, but didn't I account for that in the original code by extending the range by n+1 and n-1 from both sides? Is extending it to plus minus 2n really necessary? The values of n in the final version of the program will be really large. – QDots Mar 6 '18 at 10:46
• I found a simpler solution. See my edit. – Henrik Schumacher Mar 6 '18 at 14:27