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
--
https://mail.python.org/mailman/listinfo/python-list
