In Mathematica, why is it that a replacement in a recursive function doesn't terminate?

Question

Imagine I've defined a recursive factorial in Mathematica, like this:

Clear[fact]
fact[0] = 1
fact[n_] := n fact[n - 1]

Evaluating fact[10] confirms that the function works and terminates.

A bit of a staple example, but it serves its purpose in this question. Actually, my question pertains to recursive function definitions in general anyway.

I expected evaluating the following replacement to terminate as well:

x fact[x-1] /. x -> 2

Alas, it runs in to a recursion depth limit:

$RecursionLimit::reclim: Recursion depth of 256 exceeded.

I expected to see something like:

2 fact[2-1]

or just the value

2

UPDATE: An alternative recursive definition of fact does work as expected:

Clear[fact]
fact[n_] := If[n < 1, 1, n fact[n - 1]]

But this fact (pun intended ;-) makes it even more mysterious to me: Why does it behave so much differently?

My question is twofold:

1. Even with the built-in help and searching the net for clues, I can't explain why Mathematica insists in, apparently, keeping the symbolic result, rather than evaluating the 'intermediate' results and terminating nicely. Who ventures a viable explaination?

2. How can I convince Mathematica to perform according to my expections (Other than using the alternative using If[])?

I'm really puzzled by this one, and I really hope someone out there can help me out.

/Twan

Answer 1

Trying u[x_] := x; Trace[x*u[x] /. x -> 2], it first evaluates x and u[x]. In your case, then, it first tries to evaluate fact[x-1] before replacing x by 2, and hits the recursion limit.

Attributes[ReplaceAll] shows that it does not have attribute HoldFirst, so it starts by evaluating its first argument. For instance,

ReleaseHold@ReplaceAll[Hold[x*fact[x - 1]], x -> 2]

gives the expected 2, as it holds the first argument, replaces, then releases the hold, as you intended.

Another way to do it is

Unprotect[ReplaceAll]
SetAttributes[ReplaceAll, HoldFirst]
ReplaceAll[x*fact[x - 1], x -> 2]

but don't do this.

Surely someone will give a better explanation soon, though.

EDIT: In response to the added question as to why

Clear[factif]
factif[n_] := If[n < 1, 1, n factif[n - 1]]

does not result in infinite recursion: defined this way, factif[x] evaluates to If[x < 1, 1, x factif[x - 1]], since x<1 cannot be evaluated. So it remains in this form after the attempted evaluation of the first argument of ReplaceAll, then the replacement occurs etc.

Answer 2

This is because you're evaluating this:

fact[x-1]

before the replacement happens. Just do fact[x-1] and you get the error.

You can fix your fact function like so:

Clear[fact]
fact[0] = 1
fact[n_Integer?Positive] := n fact[n - 1]

Then x fact[x - 1] /. x -> 2 returns 2 which seems correct.

Remember that your function argument pattern fact[n_] is extremely general. For example it allows for something like fact[Integrate[Sin[x], x]] to evaluate, which is probably not something you intended. Using fact[n_Integer] is much more precise, and will allow the fact function to act the way you want it to.

If you want to define this function even better, you can do something like:

Clear[fact]
fact::nicetrybuddy = "fact[``] is not defined.";
fact[0] = 1
fact[n_Integer?Positive] := n fact[n - 1]
fact[n_] := (Message[fact::nicetrybuddy, n]; $Failed)

So that something like fact["x"] will fail with a message:

fact::nicetrybuddy: fact[x] is not defined.