[Tutor] fibonacci

[Gregor Lingl]

alan.gauld@bt.com schrieb:

>>>...
>>>
>  
>
>>I would not recommend creating a second order (containing two 
>>recursive elements e.g. "fib (n - 1)" and  "fib (n - 2)" ) 
>>    
>>
>
>I'm curious, why not?
>(Aside from performance maybe which is just as true with any 
>recursive solution.)
>  
>
This definitely has to be seen more differentiating ... (YKWIM?)

Consider

def fib1(n, a=0, b=1):
    if n == 0:
        return a
    else:
        return fib1( n-1, b, a+b)

and

def fib2(n):
    if n < 2:
        return n
    else:
        return fib2(n-2) + fib2(n-1)

Launching

 >>> for i in range(30):
    print fib(i)

with fib beeing fib1 or fib2 you can literally see the difference.

For instance:
fib1(24) needs 24 recursive calls (because this version is eqivalent to 
a simple for-loop),
while
fib2(24) needs more than 150000 recursive calls, the number of recursive 
calls growing
(approx) geometrically with n.
So it certainly will be definitly *impossible* to compute fib2(100), 
while my previously
posted fib1liner computes the first 1000 Fibonacci numbers in far less 
than 1 second.

Convincing?

Gregor

>Alan g.
>
>_______________________________________________
>Tutor maillist  -  Tutor@python.org
>http://mail.python.org/mailman/listinfo/tutor
>
>
>  
>