Comments on: Re: Python recursion performance test

By: Nicolas

Nicolas — Tue, 04 Aug 2009 18:20:53 +0000

More discussion going on at http://geekfromcairo.wordpress.com/2009/08/04/to-understand-recursion-you-need-to-understand-recursion-take-2/#comment-39 and before…

By: To Understand Recursion You Need To Understand Recursion… « Another Geek from Cairo

Sat, 01 Aug 2009 01:39:24 +0000

[...] rightly concluded that recursion in Python is slow. (An interesting counter-gument can be found here as [...]

By: Mohammed Gamal

Mohammed Gamal — Fri, 31 Jul 2009 23:49:31 +0000

Great reply! However, I think that even with memoization you’re very likely to hit recursion limits in python, since you still call the function recursively, and in my experience python doesn’t really hold a huge space for the call stack. Try for example running fib2(1000) from first run, where you’ll hit the limit, now try fib2(900) then fib2(1000), you’ll immediately get the result since you only did 100 recursive calls this time.
Bottom line, you may use recursion in python, but you gotta bit a little bit more careful when designing your algorithms than other compiled programming languages

By: James Henstridge

James Henstridge — Fri, 17 Jul 2009 03:28:19 +0000

Mohamed: I do use recursion in Python (e.g. for processing tree data structures) — I just don’t use it in cases where I am going to hit the recursion limit. Python has other tools for those sort of situations (ones that leave you with a readable stack trace when things go wrong too).

Furthermore, the naive recursive fib() implementation given here can’t take advantage of tail call optimisation anyway, due to it not simply returning the result of another function call.

To take advantage of tail call optimisation, you’d need an implementation like:

def fib_helper(x, y, n):
if n == 0: return x
return fib_helper(y, x + y, n – 1)
def fib4(n):
return fib_helper(0, 1, n)

While I agree that my fib3() implementation is slightly more difficult to read than the original naive fib() implementation, it isn’t clear to me that fib4() is better. If I was using a different language, things might tip in the other direction, but we are talking about Python here.

By: Mohamed Fawzy

Mohamed Fawzy — Thu, 16 Jul 2009 18:36:59 +0000

it is an intelligent solution James,But am i supposed not to use recursion at all in Python,i wish there is a plan for optimizing the python interpreter functions call.
I think programmers should be able to choose their problem solving technique,not to be compelled to avoid using someone i mean recursion here.

By: James Henstridge

James Henstridge — Thu, 16 Jul 2009 09:02:59 +0000

In your fib2() function, you construct a list of all the Fibonacci numbers up to the point in the sequence you’re asked for. This means that it’s memory requirements will be proportional to the number you ask for: the same problem with naive recursive solutions.

But each iteration of the loop only requires access to the previous two items in the sequence, so you could get away with only storing those two items. Something like this should be sufficient:

def fib3(n):
if n == 0 or n == 1: return n
x, y = 0, 1
for i in xrange(n-1):
x, y = y, x + y
return y

It’d be interesting to see how Unladen Swallow fairs with this version: as well as getting rid of the list reallocation, it also moves the logic to be in terms of local variables which should be easier to optimise.