fibonacci series what Iam is missing ?

[Steven D'Aprano]

Given the standard recursive version of the Fibonacci series:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

I asked:

> The question is, just how inefficient is is? How many calls to `fib` are
> made in calling fib(n)?

The answer follows the spoiler space. Try solving the question yourself
before reading the answer.



*
*
*
*
*


 
S
P
O
I
L
E
R


 
S
P
A
C
E


 
*
*
*
*
*



fib(0) makes no recursive calls, so the answer for n = 0 is 1.

fib(1) makes no recursive calls, so the answer for n = 1 is 1.

fib(2) makes two recursive calls, fib(1) and fib(0), so the answer 
for n = 2 is 3.

fib(3) makes two recursive calls, fib(2) and fib(1). They in turn make 3 and
1 calls each, so the answer is 5:
    1 for the call to fib(3)
    +3 for the call to fib(2)
    +1 for the call to fib(1)

fib(4) makes two recursive calls, fib(3) and fib(2), giving 9 calls in
total:
    1 for the call to fib(4)
    +5 for the call to fib(3)
    +3 for the call to fib(2)

This is a recursive relationship very similar to the Fibonacci series! Let's
call the function "number of subroutine calls made by fib(n)" L(n), for
reasons which will become clear later:

def L(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return L(n-1) + L(n-2) + 1


This number grows significantly faster than the Fibonacci series itself.
Here are the first few values:

---  --------  ---------
n    Fib(n)    L(n)
---  --------  ---------
0    0         1
1    1         1
2    1         3
3    2         5
4    3         9
5    5         15
6    8         25
7    13        41
8    21        67
9    34        109
10   55        177
11   89        289
12   144       465
...
35   9227465   29860703
---  --------  ---------


L(n) is in fact a standard mathematical sequence, the nth Leonardo Number.


What if we ask the same question of Leo, that is, how many function calls
does Leo(n) make?

The number of function calls needed to calculate the nth Leonardo Number
using this recursive algorithm is ... the nth Leonardo Number. So in a way,
we need not actually bother calculating anything, but just count the number
of function calls, throwing away the intermediate results! I think that is
rather neat.

http://en.wikipedia.org/wiki/Leonardo_number



-- 
Steven