What is not tail recursion

Does Python optimize tail recursion?

Edit (2015-07-02): Over time my answer has become very popular and since it was initially more of a link than otherwise I decided to take some time and rewrite it from scratch (however, you will find the first answer at the end).

Edit (2015-07-12): I finally published a module that does tail call optimization (both tail recursion and continuation passing style): https://github.com/baruchel/tco

Tail recursion optimization in Python

It has often been suggested that tail recursion is not appropriate for the Pythonic type of coding and that one shouldn't care about how to put it inside a loop. I do not want to argue with this point of view. However, sometimes I like to try or implement new ideas as recursive functions instead of loops for various reasons (I focus on the idea rather than the process, have twenty short functions on my screen at the same time instead of just three " Pythonic "functions, working in an interactive session instead of editing my code, etc.).

Optimizing tail recursion in Python is quite simple indeed. While it is described as impossible or very difficult, I think that this can be achieved with elegant, concise, and general solutions; I even think that most of these solutions use Python's functions no differently than they should. Sanitized lambda expressions combined with very standard loops result in fast, efficient, and fully usable tools for implementing tail recursion optimization.

For personal reasons I wrote a small module that implements such an optimization in two different ways. I would like to dwell on my two main functions here.

The clean way: Modifying the Y-combiner

The Y-combiner is well known. it allows recursive use of lambda functions, but does not allow recursive calls to be embedded in a loop. Lambda calculation alone cannot do that. However, a slight change in the Y combiner can protect the recursive call that is actually to be evaluated. The evaluation can thus be delayed.

Here is the famous expression for the Y combiner:

With a very small change I could get:

Instead of calling itself, the function f now returns a function that does the same call, but since it returns it, the evaluation can be done from the outside later.

My code is:

The function can be used in the following ways; Here are two examples with recursive versions of the factorial and Fibonacci:

Obviously, the recursion depth is no longer a problem:

This is of course the only real purpose of the function.

There is only one thing that cannot be done with this optimization: it cannot be used with a tail recursive function that evaluates another function (this stems from the fact that callable returned objects are all treated as further recursive calls with no distinction) . Since I don't normally need such a feature, I'm very happy with the code above. However, in order to provide a more general module, I've put a little more thought into finding a solution to this problem (see next section).

As for the speed of this process (which is not the real problem), it happens to be quite good. Tail recursive functions are even evaluated much faster with simpler expressions than with the following code:

I think that scoring an expression, even if it's complicated, is much faster than scoring multiple simple expressions, which is the case in this second version. I haven't kept this new feature in my module and I don't see any circumstances in which it could be used rather than the "official" one.

Disclosure with exceptions

Here's a more general function; It is capable of handling all recursive functions, including those that return other functions. Recursive calls are recognized based on exceptions to other return values. This solution is slower than the previous one. Faster code could probably be written by recognizing some special values ​​as "flags" in the main loop, but I don't like the idea of ​​using special values ​​or internal keywords. There's a fun take on using exceptions: if Python doesn't like tail-recursive calls, an exception should be thrown when a tail-recursive call occurs, and this will be done the Pythonian way, take the exception to find a clean solution what actually happens here ...

All functions can now be used. The following example evaluates the identity function for each positive value of n:

One could of course argue that exceptions are not intended to purposely redirect the interpreter (as some sort of statement, or probably more like some sort of continuation passing style), which I have to admit. But again, I find the idea of ​​using a single line as a statement to be funny: we are trying to return something (normal behavior) but we cannot do so due to recursive calling (exception).

First answer (08/29/2013).

I wrote a very small plugin for tail recursion handling. You can find it there with my explanations: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

It can embed a lambda function written with a tail recursion style inside another function that evaluates it as a loop.

The most interesting feature of this little function, in my humble opinion, is that the function is not based on a dirty programming hack, but on a pure lambda calculation: the behavior of the function is changed when it is inserted into another lambda function, it looks very similar to the Y-combiner.