Indexed function recursion problem

Question

I am trying to use indexed functions in a For loop; to illustrate, I give a trivial example.

f[1, x_] := x^2

Now, I can define:

f[2,x_] := f[1,x]+x

f[3,x_] := f[2,x]+x

and the results are as expected, x^2 +x and x^2 + 2x, respectively. However, when I use the For loop

For[j = 1, j < 6, j++, f[j + 1, x] := f[j, x] + x]

I get the following error message:

$RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation of f[j,x].

What gives? (the real function I need to work with is a parametric integral, so the := definition is necessary).

thanks.

Answer 1

• Rule of thumb 1: Don't use For. It's got no added value over Doand is more apt to bit you.
• Rule of thumb 2: If you're using recursion, ask yourself if you actually need it.
• Rule of thumb 3: use functional programming.

Applying these we get this:

fNoRec[n_, x_, fBase_, fInc_] := 
  Nest[# + fInc[x, #] &, fBase[x], n - 1];

Since I don't know your real problem I made this more general for you than it probably needs to be but it works like this:

• Compute the base case
• At each following step apply some incrementation function to your base value and current value
• Do this n-1 times (to get the full n iterations)

This reproduces what you seemed to want:

Table[fNoRec[n, x, #^2 &, # &], {n, 3}]

{x^2, x + x^2, 2 x + x^2}

One thing worth noting is that if you can use only pure Function constructs in fInc you'll get better performance than using a SetDelayed function.

Of course your original issue can just be solved with With and using a base case:

bad[1, x_] := x^2;
Do[With[{j = j}, bad[j + 1, x_] := bad[j, x] + x], {j, 6}]

bad[2, x]

x + x^2

bad[3, x]

2 x + x^2

Answer 2

It looks like what you are trying to do is a 2D recursion. This can be done straightforwardly:

f[n_, x_] := f[n, x] = f[n - 1, x] + x;
f[1, x_] = x^2;

The first line defines f[n, x] in terms of the previous f[n-1,x] and the second line provides a starting point for the recursion in n. You can use this:

f[3,x]
2 x + x^2

or get a collection of f's at once:

f[#, x] & /@ Range[7]
{x^2, x + x^2, 2 x + x^2, 3 x + x^2, 4 x + x^2, 5 x + x^2, 6 x + x^2}

Of course you can make the functions much more complicated if that is your real problem. No explicit looping (Do or For or Nest or Table) is needed. With thanks to b3m2a1 for the reminder to memoize.

Answer 3

Clear[f, n, x]

eqns = {f[1, x] == x^2, f[n, x] == f[n - 1, x] + x};

Using RecurrenceTable and FindSequenceFunction

seq = RecurrenceTable[eqns, f[n, x], {n, 7}]

(* {x^2, x + x^2, 2 x + x^2, 3 x + x^2, 4 x + x^2, 
    5 x + x^2, 6 x + x^2} *)

The closed-form is

f[n_, x_] = FindSequenceFunction[seq, n]

(* -x + n x + x^2 *)

Or using RSolve

Clear[f, n, x]

The closed form is again

f[n_, x_] = f[n, x] /. RSolve[eqns, f[n, x], {n, x}][[1]]

(* -x + n x + x^2 *)