# Tips for Tail Call Recursion in Python [duplicate]

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?

-

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

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

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.

-
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