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

[ssecorp]

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.


(the classic easy-redable exponential fib-function can obv be helped
enormously with memoization though.)

 

[Marc Christiansen]

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

Because python does no tail-call optimization.

Ciao
Marc

 

[Terry Reedy]

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.

The stack problem, by the way, is one reason linear induction is usually
written in Python with iteration syntax instead of recursion syntax.
Another is the extra simplicity.

def fib(n):
a,b = 1,0
while n:
a,b,n = b, a+b, n-1
return b

A third is the ease of conversion to a (space-efficient) generator function.

def fib_gen()
a,b = 1,0
while True:
yield b
a,b = b, a+b

The generator it produces can be used, for instance, to fill a list
(linear memo) 'on demand'.

A model that leads to the linear algorithm (as opposed to the double
recursion derived from Fibonacci's rabbit model) is as follows:
A population consists of juveniles and adults. In one period, juveniles
become adults (which never die) and adults birth (or bud off) one
juvenile. (Yeast are somewhat like this.) At time 0, we start with 1
juvenile and 0 adults. How many adults are there at time n?

Terry Jan Reedy

 

[Fuzzyman]

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

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(...)

Michael Foord
http://www.ironpythoninaction.com/

 

[Lie]

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.