9
$\begingroup$

The following recursive functions respectively calculate the length of a Short-cut Collatz Conjecture series and perform a pointless demonstration recursion:

colLength[m_] :=   Module[{}, Return[If[m == 1, 1, 1 + colLength[If[EvenQ[m], m/2, (3*m + 1)/2]]]]];
recur[n_] := If[n > 1, recur[n - 1], 1];
colLength[63728127]

(* $RecursionLimit::reclim: Recursion depth of 1024 exceeded. >>*)
(* Hold[3 112103 + 1] *)

recur[6000]

(* $IterationLimit::itlim: Iteration limit of 4096 exceeded. >>*)
(* Hold[recur[3953 - 1]] *)

So, why is one complaining about the Recursion depth and the other about the Iteration limit? I end up having to set both in my programs because I don't understand which does what.

Also, interestingly, recur appears to be pooping out after 2048 calls not 4096.

$\endgroup$
2
  • 8
    $\begingroup$ The answer becomes clear when you analyze what the tail recursion and execution stack mean in Mathematica. I gave such an analysis here. The main point is that rules which rewrite expression in their entirety (rather than their parts), do not grow the expression stack, and lead to iteration rather than recursion. The limit of such iteration is set by $IterationLimit, and your second example is of that type. Your first example, however, grows the stack, for reasons very similar to what I described in that post - and so is controlled by $RecursionLimit. $\endgroup$ Commented Jun 17, 2015 at 23:20
  • 1
    $\begingroup$ If you want to do experiments with setting $IterationLimit and $RecursionLimit, you can use TracePrint[] along with something like Block[{$IterationLimit = 16, $RecursionLimit = 8}, (* stuff *)] $\endgroup$ Commented Jun 18, 2015 at 0:11

1 Answer 1

8
$\begingroup$

There is not much to add to the explanation Leonid gave in his comment and above all in his answer about tail-recursion. Probably only one thing that might be additionally interesting in your situation are two collatz functions that look alike but one hits $IterationLimit and the other hits $RecursionLimit.

First the iterative one:

collatzIt[m_] := collatzIt[m, 0];
collatzIt[1, n_] := n + 1;
collatzIt[m_ /; EvenQ[m], n_] := collatzIt[m/2, n + 1];
collatzIt[m_, n_] := collatzIt[3 m + 1, n + 1];

Ignore the first line because it's only for convenience. Other than that, you see that all right hand sides of the definitions rewrite the complete expression. This means, although we dive recursively into another collatzIt call, there is no other expression (like 1+..) that Mathematica needs to remember. It can just evaluate the next collatzIt and use whatever this brings as result as the entire result.

You see that we remember the current length by dragging it all the way through each function-call. On each call, we increment the counter n by one.

Contrary to this is a recursive definition, that does not really count the length of the sequence. Instead, it pushes 1+... over and over again and waits for Mathematica to add everything at the end:

collatzRe[1] = 1;
collatzRe[m_ /; EvenQ[m]] := 1 + collatzRe[m/2];
collatzRe[m_] := 1 + collatzRe[3 m + 1];

It should be clear that the 1+... need to be remembered somewhere. This somewhere is the Stack. Now we could test both functions:

$RecursionLimit = 100;
$IterationLimit = 100;
collatzIt[63728127]
collatzRe[63728127]

Mathematica graphics

But there is probably one interesting subtlety: As you might know, definitions like the above are nothing more than replacement rules. One funny fact is that we could use rules directly in your case. So let's write a rule that acts like collatzIt. We start with {n,1} where n is the number and the last 1 will be used to count how long the sequence is. We stop when n==1 and do the collatz rule otherwise:

{63728127, 1} //. {n_, m_} :> 
  If[n == 1, {n, m}, {If[EvenQ[n], n/2, 3 n + 1], m + 1}]
(* {1, 950} *)

As it turns out, this kind of replace repeated will work and won't restricted by $IterationLimit or $RecursionLimit but by an option:

Options[ReplaceRepeated]
(* {MaxIterations -> 65536} *)

Finally, to be on the safe side with your function, you should use Nest or a simple dull While loop. This runs forever if it has to and you don't need to think about the different limits:

collatzNest[m_] := Last@NestWhile[With[{n = First[#]},
     {If[EvenQ[n], n/2, 3 n + 1], Last[#] + 1}] &, {m, 1}, 
   First[#] =!= 1 &]

collatzWhile[m_] := Module[{tmp = m, n = 1},
  While[tmp =!= 1,
   n++;
   tmp = If[EvenQ[tmp], tmp/2, 3 tmp + 1]
   ];
  n
  ]
$\endgroup$
3
  • 1
    $\begingroup$ This is very insightful. Thank you for taking the time to put it together. (+1 of course) $\endgroup$
    – MarcoB
    Commented Jun 18, 2015 at 2:37
  • 1
    $\begingroup$ Yes, thank you for this. Leonid's answer is a bit involved and hard for a relative noob to follow, so your simple clear explanation really helped. $\endgroup$ Commented Jun 18, 2015 at 4:22
  • $\begingroup$ @JerryGuern I agree. You might want to Accept this then? $\endgroup$
    – Mr.Wizard
    Commented Jul 22, 2015 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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