On May 17, 9:36 am, rusi <rustompm...@gmail.com> wrote: > On May 17, 8:50 pm, RJB <rbott...@csusb.edu> wrote: > > > > > > > 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 Lurkerhttp://www.csci.csusb.edu/dick/cs320/lab/10.html > > ------------------------------------------------------------- > Its an interesting problem and you are 75% there. > You see the halving gives you logarithmic behavior and the double > calls give exponential behavior. > > So how to get rid of double calls? Its quite simple: Just define your > function in terms of return pairs of adjacent pairs ie (fib(n), fib(n > +1)) for some n rather then a single number fib(n) > > Here's a straightforward linear function: > > def fp(n): #fibpair > if n==1: > return (1,1) > else: > a,b = fp(n-1) > return (b, a+b) > > def fib(n): > a,b = fp(n) > return a > > --------------- > Now use this (pairing) idea with your (halving) identities and you > should get a logarithmic algo. > > [If you cant do it ask again but yes its fun to work out so do > try :-) ]
Thank you! Very cool and clear. I hoped that there was something that Python made natural I couldn't see after 50 years in other languages. I'd like to work on combining both approaches. It may take a while... -- http://mail.python.org/mailman/listinfo/python-list
