Fibonacci: How to think recursively

[Chris Rebert]

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