Recursive Python Considered Harmful

It somewhat recently occurred to me that recursion, despite it cleanliness, improves readability at a significant cost in memory. By piling on the stack trace, at best we get a function that uses O(n) memory, and quite possibly even one that is even worse. Given that any recursive function can be written using a while loop with O(1) memory bounds, recursion seems quite a poor choice for all practical purposes.

I brought this up at work and Alexey explained that while this is true, many (particularly, functional) compilers are intelligent enough to optimize the code for you if you use tail-recursion. Being unaware of the concept, I looked up how to convert a regular recursive function into a tail-recursive function and discovered I was wasting my time since Guido has decided not to implement tail-recursion in Python.

This begs the question then, is recursion ever useful in Python or should we go back to our code and start writing those while loops?

As I see it, there is only one reason to use recursion in Python and that is when you plan to memoize your function (which makes the function take up O(n) memory anyway). (Additionally, it may be helpful to write functions out as recursive functions in order to assist in proving things, but I think, again, the function would almost certainly need to be memoized or transformed.)

In all other cases, I believe while loops are the way to go. Besides the obvious problems with memory, there are a few other points worth mentioning.

For one, Python caps the stack height at 1000. While for some functions this may be okay, if you have any interest in scaling, this limit is way too small.

Additionally, function call overhead is Python is extremely slow. (Source: the official Python wiki.)

Anyway, that’s my two cents.