In Mathematica, why does the replacement in a recursive function not end?

Question

Imagine that I defined a recursive factorial in Mathematica, for example:

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

Evaluation of the fact [10] confirms that the function works and ends.

A little basic example, but it serves its purpose in this matter. Actually, my question in the general case relates to the definitions of recursive functions.

I expected the following replacement to replace as well:

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

Alas, it works with a recursion depth limit:

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

I expected to see something like:

 2 fact[2-1] 

or just the meaning

 2 

UPDATE: an alternative recursive fact definition works as expected:

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

But this fact (pun ;-) makes it even more mysterious for me: why does he behave differently?

My question is twofold:

• Even with the built-in help and network search for hints, I cannot explain why Mathematica insists that it preserves a symbolic result, rather than evaluating the “intermediate” results and finishes beautifully. Who offers a viable explanation?

• How can I convince Mathematica to do as expected (other than using an alternative with If [])?

I am really puzzled by this and I really hope that someone out there can help me.

/ Twan

Answer 1

Attempt u[x_] := x; Trace[x*u[x] /. x -> 2] u[x_] := x; Trace[x*u[x] /. x -> 2] u[x_] := x; Trace[x*u[x] /. x -> 2] first evaluates x and u[x] . In this case, he first tries to evaluate fact[x-1] before replacing x with 2 and falls into the recursion limit.

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

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

gives the expected 2 , because it contains the first argument, replaces, and then releases the hold, as you expected.

Another way to do this is

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

but do not do it.

Of course, someone will soon give a better explanation.

EDIT: in response to an added question about why

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

does not lead to infinite recursion: it is defined in this way, factif[x] is evaluated as If[x < 1, 1, x factif[x - 1]] , since x<1 cannot be estimated. Thus, it remains in this form after trying to evaluate the first argument of ReplaceAll , then a replacement occurs, etc.

Answer 2

This is because you rate it:

 fact[x-1] 

before replacement. Just make fact[x-1] and you will get an error message.

You can fix your fact function as follows:

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

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

Remember that your fact[n_] function argument template is extremely general. For example, this allows you to evaluate something like fact[Integrate[Sin[x], x]] , which is probably not what you expected. Using fact[n_Integer] much more accurate and allows the fact function to act the way you want.

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, something like fact["x"] will end with a message:

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

Answer 3

Other answers are correct: fact evaluates before replacing the argument. The significant problem is that you defined fact with integer values ​​in your mind and did not provide a terminal condition for non-integer input. If you did instead

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

Then the fact will be left unvalued until it finds that which corresponds to a positive integer.

You may need to collapse the replacement operator in Evaluate to then run the definition for fact after replacing its argument.

An alternative approach might be to use a pure function:

 # fact[#-1]& @ 2 

This should not be judged prematurely.