Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

This question already has an answer here:

Ok, Python doesn't have tail call optimization.

But for those who think better recursively than "looply", whats the best practices to write code??

1000 stack calls are enough for many cases, but what are the tips to conceal recursion with efficiency in Python?

share|improve this question

marked as duplicate by gnat, GlenH7, MichaelT, Kilian Foth, Robert Harvey Oct 24 '13 at 16:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

When you say "conceal" what do you mean? Like hiding the fact that you've created helper functions with different signatures? – Sean McSomething Oct 22 '13 at 19:48

1 Answer 1

Well if you're writing tail recursive algorithms, you're probably doing something like this

 def my_algo(whatever)
   if some_condition:
       return foo
   return my_algo(bar)

Since the call to my_algo is necessarily the last thing to return, it's pretty easy to translate this to

 def my_algo(whatever)
   while some_condition:
       whatever = bar
   return whatever

This is actually basically what happens with tail call optimization in most compilers anyways.

share|improve this answer
OP also seems to confuse the two, but strictly speaking this is only tail recursion. You can't handle arbitrary tail calls (of the form def f(...): ...; return g(...)) this way. – delnan Oct 22 '13 at 20:30
@delnan Yep, I clarified tail recursion in my answer, but it's a good point that python has a stack and you can't avoid it – jozefg Oct 22 '13 at 20:33
Well, in a sense you are avoiding it with workarounds like the one in this answer. There's a similar (not much uglier, but probably measuably slower) workaround for arbitrary tail calls, trampolining: def f(args): return (g, args) with a wrapper function that repeatedly does (f, args) = f(args) (can be extended to keyword arguments too). – delnan Oct 22 '13 at 20:37
@delnan: Would it be possible to use this technique to implement TCO in a JVM language (e.g. Scala or Clojure)? – Giorgio Jul 14 '14 at 17:16
@Giorgio Technically possible, yes. However, more subtle than you may think. Function calls not in tail position also needs to be wrapped with the trampolining code, making the whole thing even slower than it already is. Alternatively, perform a Continuation Passing Style transform to make all calls tail calls, but that leads to even more overhead for ordinary calls and causes a great many closure allocations. All that also greatly complicates Java interop, and a mixed language call stack (Java -> Scala -> Java -> Scala) may break the whole thing anyway. In summary, it's just not worth it. – delnan Jul 15 '14 at 6:38

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