# Recursion doesn't happen any more or doesn't happen correctly if I store the recursive relationship in a variable first

I know the following code will form a recursion:

Clear["Global*"]
u[i_, n_] := u[i - 1, n] + u[i, n - 1]
u[0, n_] := n
u[i_, 0] := i

u[2, 2]
(* => 8 *)


But if I store the recursive relationship in a variable first, the recursion will fail:

Clear["Global*"]
exp := u[i - 1, n] + u[i, n - 1]
u[i_, n_] := exp
u[0, n_] = n
u[i_, 0] = i

u[2, 2]
(* ERROR *)


Why? I guess maybe exp "shields" i and n, so, I tried something like:

Clear["Global*"]
exp := u[i - 1, n] + u[i, n - 1]
u[i1_, n1_] := (i = i1; n = n1; exp)
u[0, n_] := n
u[i_, 0] := i
u[2, 2]
Table[Table[{i, u[i, n]}, {i, 0, 2}], {n, 0, 2}];
u[2, 2]
(* =>5
=>5 *)


…As you see, it doesn't give the right answer.

A even "amazing" case is this:

Clear["Global*"]
exp := u[i - 1, n] + u[i, n - 1]
u[i1_, n1_] := (i = i1; n = n1; u[i, n] = exp)
u[0, n_] := n
u[i_, 0] := i
u[2, 2]
Table[Table[{i, u[i, n]}, {i, 0, 2}], {n, 0, 2}];
u[2, 2]
(* =>5
=>14 *)


Ah…the process of recursion is so complex, how to explain all these? And, how to solve the original problem?

-

exp := u[i - 1, n] + u[i, n - 1];
u[i_, n_] := exp;


The way I think Mathematica does the evaluation of the body of u when you give the parameters 2 2, more or less, is like this:

Clear["Global*"];
exp := u[i - 1, n] + u[i, n - 1];

(* a more-or-less accurate model of function evaluation *)
Hold[exp] /. {i -> 2, n -> 2} // ReleaseHold

(* u[-1 + i, n] + u[i, -1 + n] *)


So what's happening is that there is no literal i or n symbol in the literal expression of the function. There is no i or n in exp. So by the time the Hold is released, the symbol replacement has already occurred and done nothing, and you end up with a recursive chain of no replacements. One way to force evaluation even within Hold is with Evaluate:

Clear["Global*"];
exp := u[i - 1, n] + u[i, n - 1];
Hold[Evaluate[exp]] /. {i -> 2, n -> 2} // ReleaseHold

(* u[1, 2] + u[2, 1] *)


Translating this back into the function definition:

...
u[i_, n_] := Evaluate[exp];
...


Which works as expected.

exp := u[i - 1, n] + u[i, n - 1]
u[i1_, n1_] := (i = i1; n = n1; exp)


We use the same "model" as before:

Clear["Global*"];
exp := u[i - 1, n] + u[i, n - 1];
Hold[(i = i1; n = n1; exp)] /. {i1 -> 2, n1 -> 2} (* // ReleaseHold *)

(* Hold[i = 2; n = 2; exp] *)


Where you can see that you're assigning into the global symbols of i and n. Maybe that's your intention, and if you ReleaseHold this single application evaluates to the expected expression, but I imagine it would give weird answers because of the multiple branches (after the left branch reaches bottom, those bottom-most i and n are used at the top of the right branch, I think... or something like that. brainhurt).

Mr. Wizard's Block[{i = i1, n = n1}, exp] approach is one way to accomplish the goal here. Throwing it into our evaluation model:

Clear["Global*"];
exp := u[i - 1, n] + u[i, n - 1];
Hold[Block[{i = i1, n = n1}, exp]] /. {i1 -> 2, n1 -> 2} // ReleaseHold

(* u[1, 2] + u[2, 1] *)


Which evaluates to the correct value but also works in the general case because Block keeps the scope of those i and n within its subexpressions.

A general note: Trace can come in very handy in things like this. It will show you for example whether the i and n are being replaced or not.

-
I did try that = form but it didn't work, maybe because I wasn't clearing my variables or something. But anyways, it looks like there is a difference of some kind. If you try both versions, the = version gives a recursion error because it's not delayed. The code still runs though, so I'm not sure if it makes an actual difference in usage. The DownValues are exactly the same except for = and :=. –  amr Oct 3 '12 at 9:20
@Mr.Wizard I've cleared all my variables and tried the solution with Evaluate, it works… –  xzczd Oct 3 '12 at 9:34
@xzczd you're right, these are not the same; I retract my earlier comment, and I am exploring this. –  Mr.Wizard Oct 3 '12 at 9:41
I tried to Trace my problematic codes but… brainbreak…Anyway, now I have two ways to avoid this problem, also thanks to @Mr.Wizard ! –  xzczd Oct 4 '12 at 6:43

I don't really know what you're trying to accomplish, so my apology if this doesn't answer your question in full

u[i_, n_] := u[i - 1, n] + u[i, n - 1]


This line of code creates a DownValue for u that describes a function in the form of a replacement rule, transforming the left-hand-side of := into the right-hand-side. In use, expressions which match the named patterns i_ and n_ will be substituted into the RHS in place of i and n. If i or n is not found explicitly on the RHS the expressions are simply discarded; they are not set as values to global symbols i and n.

Hopefully this description is enough for you to see that u[i_, n_] := exp cannot work. You can manually assign values (temporarily) to global symbols using Block to force it to work:

u[ii_, nn_] := Block[{i = ii, n = nn}, exp]


This is usually a bad idea however: if somehow n or i have a value set outside of this construct (which conceivably could happen in a more complicated recursion) the results will be incorrect. By comparison SetDelayed (:=) automatically scopes the variables that correspond to named patterns so this is prevented.

If you explain what you are actually trying to accomplish I may have a more helpful suggestion.

Based on your comment below you may find value in applying the transformation rules manually as follows. RuleDelayed takes the place of SetDelayed, and it shares the latter's automatic scoping.

ClearAll[u]

recursion1 =  {u[i_, 0] :> i,
u[0, n_] :> n,
u[i_, n_] :> u[i - 1, n] + u[i, n - 1]};

u[2, 2] //. recursion1


8

Be aware that the rules are tried in the explicit order given rather than the automatic ordering of DownValues. This is why I placed the zero rules first.

-
…To tell you the truth, this question is generated in the process of figuring out the mistake of PlatoManiac's answer here. In his code, it's necessary to store the recursive relationship in a variable first, and, you're right, though the trick with Block works for my sample, it's not effective for the complicated original one. –  xzczd Oct 3 '12 at 8:33
@xzczd I'm not in the mood to work though a big lump of code but I added an example to my answer that may be helpful. –  Mr.Wizard Oct 3 '12 at 8:47
Er…seems that RuleDelayed is also unable to climb over the obstacle of intermediate variable. Something like exp := u[i - 1, n] + u[i, n - 1]; recursion1 = {u[i_, 0] :> i, u[0, n_] :> n, u[i_, n_] :> exp}; u[2, 2] //. recursion1 doesn't work. –  xzczd Oct 3 '12 at 9:53
@xzczd I didn't mean to imply it would; I'm just trying to offer another way to "store the recursive relationship." –  Mr.Wizard Oct 3 '12 at 9:55