Fibonacci series recursion error

[Steven D'Aprano]

On Sun, 01 May 2011 10:27:14 +0100, Hans Georg Schaathun wrote:

> On 01 May 2011 09:04:27 GMT, Steven D'Aprano
>   <steve+comp.lang.python at pearwood.info> wrote:
> :  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:
> 
> Of course you do, but you are still only saying that there might be an
> application where this might happen because of excessive although
> logically correct recursion.  You have not given a single example where
> it actually happened.

Just google on "stack overflow crash".


> :  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.
> 
> But the recursion limit is mainly there to protect you against faulty
> base cases.  Obviously, since it measures the number of items on the
> stack and not their size.

The Python virtual machine knows how big each entry on the stack needs to 
be. (I don't, but it's got to be at least the size of a pointer.) So 
"number of items" is just a multiplication away from "size of the items".

In practice the main reason that stacks overflow is because of faulty 
base cases in recursion. That's obvious. But in principle, any 
sufficiently large number of function calls could overflow the stack. If 
the call stack is (say) 1 MB (chosen only to make the maths easier), and 
each function call requires (say) a single four-byte entry on the stack, 
then you can have a maximum of 250000 function calls before overflowing 
the stack.

If you don't like my numbers -- and you probably shouldn't, since I made 
them up -- choose your own. But whatever numbers you choose, there *must* 
be a maximum number of function calls before the stack overflows.

Not necessarily recursive function calls either: any nested function call 
will do. However, it's generally only in recursion that you have more 
than a few hundred calls on the stack.

So even if the base case is correct, you can overflow the stack. Given 
the naive recursive factorial function:

def fact(n):
    if n <= 1: return 1
    return n*fact(n-1)

and the theoretical limit above, then fact(250001) will overflow the 
stack even though the base case is correct.


-- 
Steven