|Ned Batchelder : Blog | Code | Text | Site|
» Home : Blog : May 2012
This morning in the #python IRC channel, someone needed help with a recursive function:
(Names other than mine, nedbat, are changed.) Before anyone's read Questioner's code, or even listened fully to his question, we're off on the usual rant against recursion in Python, and debates about tail-call elimination. As it happens, and as Questioner rightly understood, the problem is not about deep recursion:
Questioner wanted to call this function with 2**30, which is quite modest in terms of depth, the stack will only get 30 levels deep. But it's crazy in memory terms: it tries to allocate a list with a billion elements, but not before it's allocated and deallocated many many others, up to that size.
So yes, this function isn't going to work, but not because of tail-call optimization or its lack. We can change the function into a generator that still works recursively, but won't allocate any memory:
Talking more with Questioner, it turns out he didn't want the sequence, he wanted to be able to randomly access elements of his list. We can turn this function into a closed-form solution that computes the n'th element of this list:
This function is still recursive, and so will use up to 30 stack frames for numbers up to 2**30, but doesn't allocate any lists at all. This function is also in a simple tail-call form, so we can easily make it iterative:
BTW, this code gets to use one of the few methods on integers, bit_length(), which is new in 2.7.
In the end, we eliminated the recursion, but not for any of the reasons Naysayer was darkly hinting at.
When people say Python is bad at recursion, they are referring to the fact that the stack can't grow beyond 1000 frames. This makes it bad at the kind of recursion that languages like Scheme and Haskell encourage. This school of thought uses recursive procedures for iterative processes, to put it in terms from Structure and Interpretation of Computer Programs. Python is not good for this sort of recursion, because it won't work for more than 1000 iterations, which is far too low a limit.
But truly recursive processes don't often need that much stack, so using recursive procedures for recursive processes is fine in Python. Blanket statements like "recursion is almost always bad in Python" are just simplistic.
tagged: python» 8 reactions