Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #4392

Re: Fibonacci series recursion error

Show key headers only | View raw

On 01 May 2011 11:56:57 GMT, Steven D'Aprano
  <steve+comp.lang.python@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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: Fibonacci series recursion error Paul Rudin <paul.nospam@rudin.co.uk> - 2011-04-30 15:40 +0100
  Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-01 09:18 +0100
    Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-01 09:04 +0000
      Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-01 10:27 +0100
        Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-01 11:56 +0000
          Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-01 14:15 +0100
            Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 06:49 +1000
              Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 06:36 +0100
                Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 16:28 +1000
                Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 16:30 +1000
                Re: Fibonacci series recursion error (slightly OT) Dave Angel <davea@ieee.org> - 2011-05-02 08:50 -0400
            Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-02 01:09 +0000
              Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 10:41 +0100
        Re: Fibonacci series recursion error Terry Reedy <tjreedy@udel.edu> - 2011-05-01 18:24 -0400
          Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 14:14 +0100
            Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-02 16:41 +0000
              Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 21:02 +0100
                Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-03 00:21 +0000
                Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 20:42 -0700
                Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-03 06:13 +0100
                Re: Fibonacci series recursion error Robert Brown <robert.brown@gmail.com> - 2011-05-08 01:44 -0400
                Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-08 12:59 +0000
                Development time vs. runtime performance (was: Fibonacci series recursion error) Teemu Likonen <tlikonen@iki.fi> - 2011-05-08 19:34 +0300
                Re: Development time vs. runtime performance (was: Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-09 12:49 +1000
                Re: Development time vs. runtime performance (was: Fibonacci series recursion error) Robert Brown <robert.brown@gmail.com> - 2011-05-08 23:01 -0400
            Re: Fibonacci series recursion error Terry Reedy <tjreedy@udel.edu> - 2011-05-02 14:56 -0400
            Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 07:56 +1000
              Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-03 08:01 +0100

csiph-web