Why is this blowing the stack, thought it was tail-recursive...

[Lie]

On Jul 13, 8:44 pm, Fuzzyman <fuzzy... at gmail.com> wrote:
> On Jul 13, 7:56 am, Steven D'Aprano <st... at REMOVE-THIS-
>
>
>
> cybersource.com.au> wrote:
> > On Sat, 12 Jul 2008 19:25:18 -0400, Terry Reedy wrote:
> > > ssecorp wrote:
> > >> def fib(n):
> > >>     def fibt(a, b, n):
> > >>         if n <= 1:
> > >>             return b
> > >>         else:
> > >>             return fibt(b, a + b, n - 1)
> > >>     if n == 0:
> > >>         return 0
> > >>     else:
> > >>         return fibt(0, 1, n);
>
> > >> and can memoization speed up this even more? tesintg with memoization
> > >> doesnt really say anything because it is so fast it is instant anyway.
>
> > > Except for the fact that a+b gets slower as a and b get bigger, this
> > > would already be linear time in n.  Memoization (here by means of a
> > > linear list) only helps if the list is preserved and one makes repeated
> > > requests for various fib values.
>
> > > I am just curious what input you tried that blew the stack?  It had to
> > > be pretty large.
>
> > No, not really. Try it for yourself: on my system, I get RuntimeError:
> > maximum recursion depth exceeded with fib(999).
>
> > fib(999) is a large number, with 208 digits, but not that large:
>
> > 268638100244853593861467272021429239676166093189869523401
> > 231759976179817002478816893383696544833565641918278561614
> > 433563129766736422103503246348504103776803673341511728991
> > 69723197082763985615764450078474174626L
>
> > --
> > Steven
>
> The default CPython recursion limit is 1000 - so hitting it with an
> input of 999 is not that surprising...
>
> You can set a higher limit with sys.setrecursionlimit(...)

Though that would be a kludge, not a fix. Using iteration or generator
expression is better.