Fibonacci: How to think recursively
Chris Rebert
clp2 at rebertia.com
Sun Aug 29 06:19:05 CEST 2010
On Sat, Aug 28, 2010 at 7:25 PM, Steven D'Aprano
<steve at 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
More information about the Python-list
mailing list