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

[Terry Reedy]

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.

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