On Sat, Aug 28, 2010 at 7:25 PM, Steven D'Aprano

<(E-Mail Removed)> 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