What's the efficiency difference between these (almost identical) conditions
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?
No comments:
Post a Comment