Fibonacci series recursion error

[Hans Georg Schaathun]

On 01 May 2011 11:56:57 GMT, Steven D'Aprano
  <steve+comp.lang.python at pearwood.info> wrote:
:  Just google on "stack overflow crash".

And I get loads of examples of stack overflows, but I could not see
anybody linking this to logically correct recursion.  Wikipedia, for
instance, mentions two common causes, neither of which has anything
to do with logically correct recursion.  

:  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".

Does it?  In a conventional stack you need to store all the local
variables for the function as well.  Thus, there is no limit to how
much space a single element on the stack may require.

:                                           But in principle, any 
:  sufficiently large number of function calls could overflow 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.

But all of this is in principle, and does not constitute any valid
reason to avoid recursion in practice.  If you want to argue that
recursion is a bad thing in /practice/ you need a /practical/ argument.

There is also a limit to how far you can usefully recurse over a limited
data structure.

:  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.

Of course that will overflow, but you are now trying to calculate an
integer of several /million/ bits.  Please suggest me a current-day
application where you would want to have and also be able to use such
a number.

There are many ways to crash a system if you want to.

But if you don't deliberately try to crash it, you are much more
likely to crash it because you allocate to much memory in each step
than because the recursion gets to deep.  Consequently, because recursion
is usually a clearer form of expression than iterative loops, recursion
may actually be /less/ dangerous.


-- 
:-- Hans Georg