Menu
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!
882
If a recursion never reaches a base case, it goes on making recursive calls forever, and the program never terminates. This is known as infinite recursion, and it is generally not a good idea.
If a recursion never reaches a base case, it will go on making recursive calls forever and the program will never terminate. This is known as infinite recursion, and it is generally not considered a good idea. In most programming environments, a program with an infinite recursion will not really run forever.
To prevent infinite recursion, you need at least one branch (i.e. of an if/else statement) that does not make a recursive call. Branches without recursive calls are called base cases; branches with recursive calls are called recursive cases.
The maximum recursion depth in Python is 1000. You can change the limit by calling sys. setrecursionlimit() method.
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)
178
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.
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
