On Sat, Aug 28, 2010 at 7:25 PM, Steven D'Aprano <st...@remove-this-cybersource.com.au> wrote: > On Sat, 28 Aug 2010 16:12:36 -0700, Baba wrote: >> Level: beginner >> >> I would like to know how to approach the following Fibonacci problem: <snip> >> my attempted rough code: >> >> def fibonacci(n): >> # base case: >> result = fibonacci (n-1) + fibonacci (n-2) >>>> this will end up in a mess as it will create overlapping recursions > > Mathematically, there is nothing wrong with overlapping recursion. It > will work, and Python can handle it easily. > > But in practical terms, it can lead to great inefficiency. In this > example, it should be avoided because it is slow. Very slow. To calculate > the nth Fibonacci number using naive recursion requires *many* calls: > > fib(4) # first call > => fib(3) + fib(2) # three calls > => fib(2) + fib(1) + fib(1) + fib(0) # seven calls > => fib(1) + fib(0) + 1 + 1 + 0 # nine calls > => 1 + 0 + 1 + 1 + 0 = 3 > > So to get fib(4) = 3 requires nine calls to fib(). > > This growth function doesn't have a name (as far as I know),
It's A001595 in OEIS; http://www.research.att.com/~njas/sequences/A001595 "Sometimes called 'Leonardo numbers'" Also apparently "2-ranks of difference sets constructed from Segre hyperovals." > but it grows > much faster than fib() itself: > > n = 0 1 2 3 4 5 6 ... 35 ... > fib(n) = 0 1 1 2 3 5 8 ... 9227465 ... > calls = 1 1 3 5 9 15 25 ... 29860703 ... > > As you can see, the number of calls is also calculable by a recursive > expression R: > > R(0) = R(1) = 1 > R(n) = R(n-1) + R(n-2) + 1 > > This is very similar to the Fibonacci recursion, only it grows more > quickly. But I digress... Other formulations courtesy OEIS: R(n) = sum(fib(i) for i in range(1, n+1)) - fib(n-1) R(n) = 2*fib(n+1) - 1 Cheers, Chris -- http://blog.rebertia.com -- http://mail.python.org/mailman/listinfo/python-list
