4
$\begingroup$

Given a recursive function, is there some simple way to display or store the value of recursion or "how many levels deep" the function is at a given time?

For instance, if we wrote the recursive function to calculate the factorial of a number (for any positive integer x):

r[x_] := If[x > 0, x*r[x - 1], 1]

Is there some way to output, as the function evaluates that it is a level "n"?

Given that the $RecursionLimit determines the max number of times a function can call itself nested, there must be some flag or value stored to keep track of how deep the current evaluation is that is compared to $RecursionLimit, that, if exceeded, aborts. What is this flag/value?

$\endgroup$
  • 1
    $\begingroup$ From Stack documentation: "The maximum length of Stack[] is limited by $RecursionLimit." $\endgroup$ – Oleksandr R. Jan 18 '15 at 1:26
  • 1
    $\begingroup$ @Oleksandr The question how is (I believe) how can you access the present depth before $RecursionLimit is reached. $\endgroup$ – Mr.Wizard Jan 18 '15 at 1:29
  • 1
    $\begingroup$ @Mr.Wizard the documentation I quoted implies that the correct thing to do is Length@Stack[]. I am not sure if Stack[] is really the most fundamental manifestation of the evaluation stack, but even if not, I think it should suffice. Add StackBegin/StackInhibit to taste. $\endgroup$ – Oleksandr R. Jan 18 '15 at 1:32
  • $\begingroup$ @Oleksandr Okay, I missed that point. Thanks. Have you tested it? Can you help me find the earlier question? $\endgroup$ – Mr.Wizard Jan 18 '15 at 1:36
  • $\begingroup$ @Mr.Wizard stackoverflow.com/questions/7414601/…? I am not sure exactly which question you must be thinking of, but this seems close. $\endgroup$ – Oleksandr R. Jan 18 '15 at 1:49
4
$\begingroup$

The obvious way to modify your code is

Clear[f, r]
r[x_, n_] := If[x > 0, Print[n]; x*r[x - 1, n + 1], 1]
f[k_Integer /; k > 1] := r[k, 1]

For small values of x, this works fine.

f[5]

f[5]

But it is very inefficient and also limited by $RecursionLimit.

Block[{$RecursionLimit = 20}, f[24]]

aborted-f[24]

Both these issues can be addressed by using a less obvious tail-recursive version of r.

Clear[f, r]
r[0, val_, _] = val;
r[k_ /; k > 0, val_, n_] := r[k - 1, k val, Print[n]; n + 1]
f[k_Integer /; k > 0] := r[k - 1, k, 1]

Block[{$RecursionLimit = 20}, f[24]]

tail-f[24]

$\endgroup$
  • $\begingroup$ +1 for tail recursion, I wasn't aware that you could use it in Mathematica (although it seems obvious now). $\endgroup$ – 2012rcampion Jan 25 '15 at 4:05
  • $\begingroup$ @2012rcampion see (4481301) and (21746) $\endgroup$ – Mr.Wizard Jan 25 '15 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.