5
$\begingroup$

This question already has an answer here:

When I investigate Fibonacci's series

fib[n_] := fib[n] = fib[n - 1] + fib[n - 2]
fib[0] = fib[1] = 1;
Block[{$RecursionLimit = 10^4}, fib[10^3]]

I can evaluate it for n=10^3. However, if I do the following

fib[n_] := fib[n] = fib[n - 1] + fib[n - 2]
fib[0] = fib[1] = 1;
Block[{$RecursionLimit = 5*10^4}, fib[10^4]]

I get a beep, the kernel quits and the message "The kernel Local has quit (exited) during the course of an evaluation" shows up.

Is this error beep due to memory restrictions (since I memorize too many values)? However, I don't see anything in the Linux' top overview.

$\endgroup$

marked as duplicate by m_goldberg, LCarvalho, Coolwater, gwr, MarcoB Nov 20 '17 at 18:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ since I memorize too many values? But you memoize only 10^4. ByteCount@DownValues@fib returns about 7MB for me. Probably a local problem, try restarting the kernel. $\endgroup$ – LLlAMnYP Nov 16 '17 at 9:43
  • $\begingroup$ Yes, that's exactly what I thought. Tried to restart it now for several times, problems remains unfortunately. $\endgroup$ – Display Name Nov 16 '17 at 10:35
  • $\begingroup$ Your specific question about the Fibonacci numbers can be handled using the built-in function Fibonacci without any worries about memory. $\endgroup$ – bill s Nov 16 '17 at 13:38
  • $\begingroup$ Fibonacci was just an example to treat a more general problem. But thanks for the hint! $\endgroup$ – Display Name Nov 16 '17 at 14:34
  • 1
    $\begingroup$ BTW: Fibonacci numbers can be calculated without using recursion $\endgroup$ – mgamer Nov 16 '17 at 21:47
16
$\begingroup$

The kernel crashes due to stack overflow. It is not safe to recurse too deeply. Increasing $RecursionLimit to values that are too great (and actually recursing that deep) risks a crash.

(So yes, in a way it's due to insufficient memory, but it has nothing to do with memoization. It is due to insufficient stack space.)

From the documentation:

On most computers, each level of recursion uses a certain amount of stack space. $RecursionLimit allows you to control the amount of stack space that the Wolfram Language can use from within the Wolfram Language. On some computer systems, your whole Wolfram Language session may crash if you allow it to use more stack space than the computer system allows.

What you can do in the most general case using memoization is to invoke the functions with gradually increasing parameter values, allowing it to memoize the results. This will limit the depth of the recursion compared to the situation when you pass the highest parameter immediately.

Block[{$RecursionLimit = Infinity}, Table[fib[ 10^3 k], {k, 1, 10}]]

What you should try to do is transform the recursion into iteration. This also avoids the exponential complexity of fib without requiring memoization.

Nest[{Last[#], First[#] + Last[#]} &, {1, 1}, 10^5]

Of course, there are explicit formulas for Fibonacci numbers (though they're not necessarily easy to compute accurately) and Mathematica also has Fibonacci.

$\endgroup$
  • 4
    $\begingroup$ So does this question belong on mathematica.stackoverflow.com instead? (Sorry, couldn't resist) :p $\endgroup$ – Marius Ladegård Meyer Nov 16 '17 at 12:06
  • 1
    $\begingroup$ @LLlAMnYP I suspect it is the call stack provided by the operating system that overflows. We don't know how Mathematica uses that stack. It might be allocating too many things on the stack instead of the heap for better performance (and the amount of space it allocates may depend on the particular expression being evaluated). Also, call stacks tend to be small. On OS X, the default is only 8 MB. I don't have an answer for you, but I do not think the crash is surprising. $\endgroup$ – Szabolcs Nov 16 '17 at 15:43
  • 1
    $\begingroup$ But I think an interpreter could be implemented in a way that it can avoid crashes due to stack overflow, perhaps by creating its own stack in which it can detect the overflow before it's too late. $\endgroup$ – Szabolcs Nov 16 '17 at 15:44
  • 1
    $\begingroup$ (2) 5*10^4 really is "that deep" for many machines/OSs. There is a multiplier involved in that internally recursion is measured by certain evaluator calls that each amount to several function calls. The multiplier for typical cases is something like 4 or 5 I believe. $\endgroup$ – Daniel Lichtblau Nov 16 '17 at 17:17
  • 1
    $\begingroup$ (3) Over time many functions that use recursion have been moved to maintaining what amounts to their own stacks. Early efforts in this direction involved Flatten, I think that was around 20 years ago. Getting the entire evaluator off the OS subroutine stack is a far more difficult and ambitious thing to do and I doubt it will ever be attempted. This applies to the Print formatting code as well. In addition to just being plain difficult to code, there would be speed implications as well, and all for dubious gain. $\endgroup$ – Daniel Lichtblau Nov 16 '17 at 17:24
2
$\begingroup$

Even assuming that you were not aware of Fibonacci, you should generally investigate simple recursions using RSolve.

Clear[fib]

fib[n_] = fib[n] /. 
  RSolve[{fib[n] == fib[n - 1] + fib[n - 2], fib[0] == 1, fib[1] == 1}, 
    fib[n], n][[1]]

(* 1/2 (Fibonacci[n] + LucasL[n]) *)

fib[10^4] // N

(* 5.443837311356528*10^2089 *)

With this approach fib is also defined for non-integer and negative arguments.

fib /@ {-7, -3.5, 0, 3.5, 7}

(* {13, 0.0829962, 0, 2.40975, 13} *)

Note also that your initial value fib[0] == 1 is not consistent with the standard definition of Fibonacci

Fibonacci[0]

(* 0 *)

Using a revised initial value fib[0] == 0

Clear[fib]

fib[n_] = fib[n] /. 
  RSolve[{fib[n] == fib[n - 1] + fib[n - 2], fib[0] == 0, fib[1] == 1}, 
    fib[n], n][[1]]

(* Fibonacci[n] *)

% // FunctionExpand

(* ((1/2 (1 + Sqrt[5]))^n - (2/(1 + Sqrt[5]))^n Cos[n π])/Sqrt[5] *)
$\endgroup$
0
$\begingroup$

There are different ways of doing recursion. f[n] = f[n-1] + f[n-2] which needs to evaluate f[n-1] until it gets a value. You can see this as an ever expanding tree of recursion just to determine the value.

With tail recursion, its a function that calls itself, but the recursion is the last statement. So you would be passing the previous two numbers in your method call, along with which fibonacci number you want.

So example: fib(0, 1, 5) where 0 is fn-1, 1 is fn, and 5 is fib number 5 we want call stack would look like this fib(0,1,5) fib(1,1,4) fib(1,2,3) fib(2,3,2) fib(3,5,1) fib(5,8,0) And then it would return 8 (I might be off by one, but hopefully this is helps)

Google Tail recursion, that will help with your memory issues

$\endgroup$
  • 1
    $\begingroup$ I will suggest coding this in the Wolfram Language and checking whether the recursion issue disappears. Otherwise it is off topic for this particular forum (I am not denying there is importance to tail recursion). $\endgroup$ – Daniel Lichtblau Nov 16 '17 at 22:30
0
$\begingroup$

A general answer from the computer science perspective:

Stack depth limits are common and exist for virtually all programming environments. As Nicolas pointed out, tail recursion is a technique for recursion which does not take up any stack space because the context of the current call (i.e. the variables in that function call's scope) are not needed for any future computations. While recursively defined functions are elegant and concise, it is sometimes necessary to write such functions iteratively to avoid stack depth limits. In theory, all recursive functions can be written iteratively.

As a desirable side effect, iterative implementations are often faster than their recursive counterparts because they cut out the overhead of making a function call and make the best use of CPU cache.

$\endgroup$
  • $\begingroup$ Again, I will suggest providing actual code showing an iterative implementation, as that would make this a more compelling response. $\endgroup$ – Daniel Lichtblau Nov 17 '17 at 15:45
  • $\begingroup$ My answer addresses the question without loss of generality. The original poster is not interested in the Fibonacci problem specifically but in avoiding stack depth limits on the general class of recursive problems. Iterative examples of Fibonacci are rather abundant on the internet. $\endgroup$ – Kevin Dice Nov 17 '17 at 20:44
  • 1
    $\begingroup$ For the purposes of this forum, your suggestion, which is a good one, is more a comment than an answer. This is because it has neither Wolfram Language code, nor link to such, to go with it. I realize there are many examples out there. Here is one in WL. Another all-around good reference is here $\endgroup$ – Daniel Lichtblau Nov 18 '17 at 16:14

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