Fibonacci: How to think recursively

News123 news1234 at free.fr
Sun Aug 29 20:35:02 CEST 2010


Hi Baba,

> So here's my code. It does still cause me one headache. If i use
> f(0)=0
> and f(1)=1 as base cases the result will be 144. I was expecting the
> result to be the next value in the series (233)...
> If i use f(1)=1 and f(2)=2 as base cases them i get my expected
> result. I assume this has to do with our understanding/defining the
> start of the Fibonacci series?
> 
> 
> def r_fib(n):
>     if n == 1: return 1
>     elif n == 2: return 2
>     else: return r_fib(n-2) + r_fib(n-1)
> 
> print r_fib(12)
> 

Let's calculate the first 12 Fobonacci numbers first manually:

0: 0 # as of its definition
1: 1 @ as of its definition
2: 0 + 1 = 1
3: 1 + 1 = 2
4: 1 + 2 = 3
5: 2 + 3 = 5
6: 3 + 5 = 8
7: 5 + 8 = 13
8: 8 + 13 = 21
9: 13 + 21 = 34
10: 21 + 34 = 55
11: 34 + 55 = 89
12: 55 + 89 = 144

So if you use f(0) = 0 and f(1) = 1 you seem to get the coorec result,
right?


Now the question is why you get the wrong result with your code:

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


The answer is very simple your result n=2 is wrong.
You wrote, that it  is 2, but it should be 1







More information about the Python-list mailing list