Is there something wrong with this python code, why does it run so slow compared to ruby?

Question

I was interested in comparing ruby speed vs python so I took the simplest recursive calculation, namely print the fibonacci sequance.

This is the python code

#!/usr/bin/python2.7                       
def fib(n):
    if n == 0: 
        return 0
    elif n == 1:
        return 1 
    else:
        return fib(n-1)+fib(n-2)

i = 0
while i < 35:
    print fib(i)
    i = i + 1

and here is the ruby code

#!/usr/bin/ruby

def fib(n)
    if n == 0
        return 0
    elsif n == 1
        return 1
    else
        fib(n-1)+fib(n-2)
    end
end 

i = 0 
while (i < 35)
    puts fib(i)
    i = i + 1 
end

over several runs, time reports this average

real    0m4.782s 
user    0m4.763s 
sys     0m0.010s

thats for ruby, now python2.7 gives

real    0m11.605s
user    0m11.563s
sys     0m0.013s

Whats the deal?

Answer 1

The recursion efficiency of python is the cause of this overhead. See this article for much more detail. The above solutions that solve this iteratively are better for python since they do not incur the function call overhead recursion does. My assumption about ruby would be that it is clearly optimizing the code while python is not. Again, that article goes into a lot detail about this using a nearly identical fib function.

Answer 2

So for this code, Python is a bit more than two times slower than Ruby. Probably for other codes, Python will be faster than Ruby.

Your implementation of fib() has exponential run time. This can easily be avoided by using a loop. Python example:

a, b = 1, 1
for i in range(35):
    a, b = b, a+b
print b