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 :-) ]
--
http://mail.python.org/mailman/listinfo/python-list
