# High Fibonacci numbers [duplicate]

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.

• 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. – LLlAMnYP Nov 16 '17 at 9:43
• Yes, that's exactly what I thought. Tried to restart it now for several times, problems remains unfortunately. – Display Name Nov 16 '17 at 10:35
• Your specific question about the Fibonacci numbers can be handled using the built-in function Fibonacci without any worries about memory. – bill s Nov 16 '17 at 13:38
• Fibonacci was just an example to treat a more general problem. But thanks for the hint! – Display Name Nov 16 '17 at 14:34
• BTW: Fibonacci numbers can be calculated without using recursion – mgamer Nov 16 '17 at 21:47

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.

• So does this question belong on mathematica.stackoverflow.com instead? (Sorry, couldn't resist) :p – Marius Ladegård Meyer Nov 16 '17 at 12:06
• @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. – Szabolcs Nov 16 '17 at 15:43
• 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. – Szabolcs Nov 16 '17 at 15:44
• (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. – Daniel Lichtblau Nov 16 '17 at 17:17
• (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. – Daniel Lichtblau Nov 16 '17 at 17:24

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] *)


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)