What's the efficiency difference between these (almost identical) conditions

Question

I was given a challenge by a friend to build an efficient Fibonacci function in python. So I started testing around different ways of doing the recursion (I do not have high math skills to think of a complex algorithm, and please do not show me an efficient Fibonacci function, that is not the question).

Then I tried two different solutions:

Solution 1:

def fibo(n):
    if n > 1:
        return fibo(n-1)+fibo(n-2)
    return 1

Solution 2:

def fibo(n):
    if n < 1:
        return 1
    return fibo(n-1)+fibo(n-2)

Then, I ran this for each:

res = map(fibo, range(35))
print res

Now, I suspected there might be an efficiency difference (I can't say why exactly). But I expected a small difference. the results blew me away completely. The difference was huge. The first one took 7.5 seconds while the second took a staggering 12.7 (that's almost twice!).

Can anyone explain to me why? Aren't those essentially the same?

Answer 1

(not n > 1) is (n <= 1), re-run the second code with <= and you will see that you get similar timings:

In [1]: def fibo(n):
   ....:    if n <= 1:
   ....:        return 1
   ....:    return fibo(n-1)+fibo(n-2)
   ....: 

In [2]: %timeit map(fibo, range(10))
10000 loops, best of 3: 29.2 us per loop

In [3]: def fibo(n):
   ....:    if n > 1:
   ....:        return fibo(n-1)+fibo(n-2)
   ....:    return 1
   ....: 

In [4]: %timeit map(fibo, range(10))
10000 loops, best of 3: 29.9 us per loop

And if you wonder why this makes such a huge difference, when you run map(fibo, range(35)) you have 14930351 calls to fibo(1). With (n < 1), each fibo(1) will make two functions calls (to fibo(0) and fibo(-1)) and sums the results, quite a few operations!

Answer 2

Aren't those essentially the same?

The second function is calculating a higher fibonacci number, so naturally it takes longer:

>>> def fibo(n):
...     if n > 1:
...         return fibo(n-1)+fibo(n-2)
...     return 1
... 
>>> fibo(10)
89
>>> def fibo(n):
...     if n < 1:
...         return 1
...     return fibo(n-1)+fibo(n-2)
... 
>>> fibo(10)
144

You likely want n <= 1 in the second snippet:

>>> def fibo(n):
...     if n <= 1:
...         return 1
...     return fibo(n-1)+fibo(n-2)
... 
>>> fibo(10)
89