I noticed some discussion of recursion..... the trick is to find a
formula where the arguments are divided, not decremented.
I've had a "divide-and-conquer" recursion for the Fibonacci numbers
for a couple of years in C++ but just for fun rewrote it
in Python. It was easy. Enjoy. And tell me how I can improve it!
def fibo(n):
"""A Faster recursive Fibonaci function
Use a formula from Knuth Vol 1 page 80, section 1.2.8:
If F[n] is the n'th Fibonaci number then
F[n+m] = F[m]*F[n+1] + F[m-1]*F[n].
First set m = n+1
F[ 2*n+1 ] = F[n+1]**2 + F[n]*2.
Then put m = n in Knuth's formula,
F[ 2*n ] = F[n]*F[n+1] + F[n-1]* F[n],
and replace F[n+1] by F[n]+F[n-1],
F[ 2*n ] = F[n]*(F[n] + 2*F[n-1]).
"""
if n<=0:
return 0
elif n<=2:
return 1
elif n%2==0:
half=n//2
f1=fibo(half)
f2=fibo(half-1)
return f1*(f1+2*f2)
else:
nearhalf=(n-1)//2
f1=fibo(nearhalf+1)
f2=fibo(nearhalf)
return f1*f1 + f2*f2
RJB the Lurker
http://www.csci.csusb.edu/dick/cs320/lab/10.html
--
http://mail.python.org/mailman/listinfo/python-list
