current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 47 down vote favorite
11

I have the following piece of code which fails with the following error:

RuntimeError: maximum recursion depth exceeded

I attempted to rewrite this to allow for tail recursion optimization (TCO). I believe that this code should have been successful if a TCO had taken place.

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

Should I conclude that Python does not do any type of TCO, or do I just need to define it differently?

share|improve this question
    
Python has no TCO implemented, It's believed to be too complex to implement in a dynamic language such as Python. –  Wessie Nov 27 '12 at 19:55
    
What is the code for initial recursion, which failed? –  gg.kaspersky Nov 27 '12 at 19:56
6  
@Wessie TCO is simple regard of how dynamic or static the language is. Lua, for example, also does it. You merely need to recognize tail calls (pretty simple, both at AST level and at bytecode level), and then re-use the current stack frame instead of creating a new one (also simple, actually even simpler in interpreters than in native code). –  delnan Nov 27 '12 at 20:02
5  
Oh, one nitpick: You talk exclusively about tail recursion, but use the acronym "TCO", which means tail call optimization and applies to any instance of return func(...) (explicitly or implicitly), whether it's recursive or not. TCO is a proper superset of TRE, and more useful (e.g. it makes continuation passing style feasible, which TRE can't), and not much harder to implement. –  delnan Nov 27 '12 at 20:11
    
Here is a hackish way to implement it - a decorator using exception raising to throw execution frames away: metapython.blogspot.com.br/2010/11/… –  jsbueno Apr 9 '13 at 23:39

4 Answers 4

up vote 63 down vote accepted

No, and it never will since Guido prefers to be able to have proper tracebacks

http://neopythonic.blogspot.com.au/2009/04/tail-recursion-elimination.html

http://neopythonic.blogspot.com.au/2009/04/final-words-on-tail-calls.html

You can manually eliminate the recursion with a transformation like this

>>> def trisum(n, csum):
...     while True:                     # change recursion to a while loop
...         if n == 0:
...             return csum
...         n, csum = n - 1, csum + n   # update parameters instead of tail recursion

>>> trisum(1000,0)
500500
share|improve this answer
4  
Or if you're going to transform it like that - just: from operator import add; reduce(add, xrange(n + 1), csum) ? –  Jon Clements Nov 27 '12 at 20:10
15  
@JonClements, that works in this particular example. The transformation to a while loop works for tail recursion in general cases. –  John La Rooy Oct 6 '13 at 23:56
    
+1 For being the correct answer but this seems like an incredibly bone-headed design decision. The reasons given seem to boil down to "it's hard to do given how python is interpreted and I don't like it anyway so there!" –  Basic Sep 4 '14 at 18:36
up vote 14 down vote

The word of Guido is at http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

I recently posted an entry in my Python History blog on the origins of Python's functional features. A side remark about not supporting tail recursion elimination (TRE) immediately sparked several comments about what a pity it is that Python doesn't do this, including links to recent blog entries by others trying to "prove" that TRE can be added to Python easily. So let me defend my position (which is that I don't want TRE in the language). If you want a short answer, it's simply unpythonic. Here's the long answer:

share|improve this answer
2  
And herein lies the problem with so-called BDsFL. –  Adam Donahue Nov 6 '14 at 20:43
1  
@AdamDonahue have you been perfectly satisfied with every decision that's come from a committee? At least you get a reasoned and authoritative explanation from the BDFL. –  Mark Ransom Nov 11 '14 at 20:22
    
No, of course not, but they strike me as more even-handed. This from a prescriptivist, not a descriptivist. The irony. –  Adam Donahue Nov 17 '14 at 0:49
up vote 10 down vote

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

It can embed a lambda function written with a tail recursion style in another function which will evaluate it as a loop.

The most interesting feature in this small function, in my humble opinion, is that the function doesn't rely on some dirty programming hack but on mere lambda calculus: the behaviour of the function is changed to another one when inserted in another lambda function which looks very like the Y-combinator.

Regards.

share|improve this answer
4  
This answer is quite interesting. Why down voted? He could show some code as a proof though. But if no code was the reason for the down vote it was no different from other highly voted answers just quoting Guido said no hence no. –  Kenji Noguchi Sep 3 '14 at 2:52
up vote 4 down vote

CPython does not and will probably never support tail call optimization based on Guido's statements on the subject. I've heard arguments that it makes debugging more difficult because of how it modifies the stack trace.

share|improve this answer
    
you mean Python ? –  mux Nov 27 '12 at 20:00
10  
@mux CPython is the reference implementation of the programming language Python. There are other implementations (such as PyPy, IronPython, and Jython), which implement the same language but differ in implementation details. The distinction is useful here because (in theory) it's possible to create an alternative Python implementation that does TCO. I'm not aware of anyone even thinking about it though, and usefulness would be limited as code relying on it would break on all other Python implementations. –  delnan Nov 27 '12 at 20:06
2  
@delnan thanks for explaining :) –  mux Nov 27 '12 at 20:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.