Fibonacci series recursion error

[Steven D'Aprano]

On Sun, 01 May 2011 09:18:36 +0100, Hans Georg Schaathun wrote:

> On Sat, 30 Apr 2011 15:40:24 +0100, Paul Rudin
>   <paul.nospam at rudin.co.uk> wrote:
> :  Anytime you have enough data... there are plenty of things that are
> natural to :  represent as recursive data structures, and often you
> don't know in :  advance how much data your code is going to have to
> deal with.
> 
> Sure, but one would think that if you can fit the data in memory, then
> you can also fit the call stack.  I can also /imagine/ that one might
> run into a limit, but I cannot see any concrete examples where it is
> likely.


Why? You might have 4000 MB of main memory, and only 2 MB (say?) of call 
stack allocated. The call stack can't grow indefinitely. If it does, you 
get a stack overflow:

http://www.ehow.com/list_6572027_reasons-stack-overflow.html

which, if you're lucky, will just crash the process. If you're unlucky, 
it will lead to an exploit that malware can use to compromise your 
machine.

In Python, the virtual machine protects you against stack overflow. 
Before the stack overflows, Python raises RecursionError. You can 
experiment by using sys.getrecursionlimit and sys.setrecursionlimit, but 
be careful, if you increase the limit too high, a deeply recursive 
function will overflow the stack.


-- 
Steven