Unwanted Hold from recursive function

Question

I am literally copying an example from a tutorial in Mathematica documentation of a recursive function, but when I evaluate I get a Hold. I don't understand why I am getting a Hold. Below is the copy and paste exactly as I see it on my console. Thank You.

f[n_] := n f[n - 1]

f[5]

Hold[5 f[5 - 1]]

Answer 1

The Problem

Your function definition does not have a "base case." When Mathematica attempts to evaluate f[5], it uses the function definition (called SetDelayed in Mathematica parlance) to rewrite f[5] as 5 f[5 - 1]. But then it encounters another instance of f and so rewrites the expression again, giving yet another instance of f. This process would iterate forever if it were not for the $RecursionLimit safety measure.

The Observed Behavior

Mathematica has a built-in stopgap for runaway recursive function calls like this one. Every time Mathematica calls a function, it increments a counter called the stack depth. When the function returns, the counter is decremented. If your function calls go too many functions deep, your stack depth will exceed the maximum allowed depth, which is given by the built-in variable $RecursionLimit (set to a default of 1024 on my system). When this happens, Mathematica emits a message (the closest thing Mathematica has to an error/warning) reporting this fact and returns a held result.

The a built-in function Trace allows you to see the intermediate expressions. In the example code below, we limit the recursion depth to 20. We also call Trace with a pattern so that it elides the intermediate expressions for subtraction and multiplication so as to only show the calls to f.

f[n_] := n f[n - 1];
$RecursionLimit = 20;
Trace[f[5], _ f[_]]

{5 f[5-1], {4 f[4-1], {3 f[3-1], {2 f[2-1], {1 f[1-1], 
{0 f[0-1],{-f[-1-1],{-2 f[-2-1],{-3 f[-3-1],
{-4 f[-4-1],{-5 f[-5-1],{-6 f[-6-1],{-7 f[-7-1],
{-8 f[-8-1],{-9 f[-9-1],{-10 f[-10-1],{-11 f[-11-1],
{-12 f[-12-1]}}}}}}}}}}}}}}}}}}

You can set $RecursionLimit to a larger or smaller number than the default, and there are situations in which it is necessary to increase $RecursionLimit in order to successfully complete a computation. One should only do so with care so as to avoid an accidentally infinite recursion that also consumes an infinite amount of memory.

When Mathematica stops the evaluation of an expression at the $RecursionLimit, it gives you a held expression of the partial result—at least, it is supposed to; see below. To continue the computation, apply ReleaseHold to the result, and it will (read should) continue to evaluate until it encounters $RecursionLimit again. The official documentation gives this simple example:

x = x + 1

255 + Hold[1 + x]

ReleaseHold[%]

510 + Hold[1 + x]

Except this is not the behavior in version 11.3. Instead, you get the original expression wrapped in Hold. I cannot find any documentation of this change in behavior. The original behavior seems quite useful to me, and the similar mechanism for $IterationLimit has not had the same change, so I wonder if it is a bug in the latest version. In any case, the Hold is meant to be there.

The Solution

While you can set $RecursionLimit to ∞, this is never a good idea. In your particular case, your function will never evaluate to a number. You need to modify your definition. The definition appears to be an incomplete attempt at defining the factorial function. If so, the definition is missing the "base case": f[0]=1.

f[0]=1;
f[n_]:=n f[n - 1];
f[5]

120

Trace[f[5], _ f[_]]

{5 f[5-1],{4 f[4-1],{3 f[3-1],{2 f[2-1],{1 f[1-1]}}}}}