Detecting Infinite recursion in Python or dynamic languages

Question

Recently I tried compiling program something like this with GCC:

int f(int i){
    if(i<0){ return 0;}
    return f(i-1);
f(100000);

and it ran just fine. When I inspected the stack frames the compiler optimized the program to use only one frame, by just jumping back to the beginning of the function and only replacing the arguments to f. And - the compiler wasn't even running in optimized mode.

Now, when I try the same thing in Python - I hit maximum recursion wall (or probably stack overflow if i set recursion depth too high).

Is there way that a dynamic language like python can take advantage of these nice optimizations? Maybe it's possible to use a compiler instead of an interpreter to make this work?

Just curious!

Answer 1

The optimisation you're talking about is known as tail call elimination - a recursive call is unfolded into an iterative loop.

There has been some discussion of this, but the current situation is that this will not be added, at least to cpython proper. See Guido's blog entry for some discussion.

However, there do exist some decorators that manipulate the function to perform this optimisation. They generally only obtain the space saving though, not time (in fact, they're generally slower)

Answer 2

When I inspected the stack frames the compiler optimized the program to use only one frame, by just jumping back to the beginning of the function and only replacing the arguments to f.

What you're describing is called "tail recursion". Some compilers/interpreters support it, some don't. Most don't, in fact. As you noticed, gcc does. And in fact, tail recursion is a part of the spec for the Scheme programming language, so all Scheme compilers/interpreters must support tail recursion. On the other hand, the compilers for languages like Java and Python (as well as most other languages, I'd wager) don't do tail recursion.

Is there way that a dynamic language like python can take advantage of these nice optimizations?

Do you mean, right now, or are you asking in more abstract terms? Speaking abstractly, yes! It would absolutely be possible for dynamic languages to take advantage of tail recursion (Scheme does, for example). But speaking concretely, no, CPython (the canonical Python interpreter) doesn't have a flag or other parameter to enable tail recursion.