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