Why is this blowing the stack, thought it was tail-recursive...
fuzzyman at gmail.com
Sun Jul 13 15:44:00 CEST 2008
On Jul 13, 7:56 am, Steven D'Aprano <st... at REMOVE-THIS-
> 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:
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(...)
More information about the Python-list