Fibonacci: How to think recursively

[Baba]

On Aug 29, 3:25 am, Steven D'Aprano <st... at REMOVE-THIS-
cybersource.com.au> wrote:

> Mathematically, there is nothing wrong with overlapping recursion. It
> will work, and Python can handle it easily.

Based on the advice by Steven and Mel i tried my initial 'guess' and
it does seem to work fine. When looking at it using pencil and paper i
thought "well, each recursive call will call 2 new ones and if n is
large i will have a huge overlap, so it probably is the wrong
approach". However it turns out to be fine in principle. It can be
handled, as Steven pointed out.


> 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:
>
> You can make it even more efficient by giving fib() a long-term cache, so
> that each call to fib(5) requires one cache lookup rather than six (or
> fifteen) recursive calls. Other than the first time, obviously. This is
> called memoisation, but again I digress.
>

I looked memoisation up and decided that for now  i will not go near
it. First i will try to build up some bacic skills but thank you very
much for the hint. Memoisation will certainly be on the list of future
exercises.

However, the idea that memoisation is needed to make the computation
more efficient confirms my initial  feeling that a 'simple' recursive
approach is somewhat not ideal.


So here's my code. It does still cause me one headache. If i use
f(0)=0
and f(1)=1 as base cases the result will be 144. I was expecting the
result to be the next value in the series (233)...
If i use f(1)=1 and f(2)=2 as base cases them i get my expected
result. I assume this has to do with our understanding/defining the
start of the Fibonacci series?


def r_fib(n):
    if n == 1: return 1
    elif n == 2: return 2
    else: return r_fib(n-2) + r_fib(n-1)

print r_fib(12)


Thanks
Baba