4

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?

Lucas Ribeiro
  • 141
  • 1
  • 3

1 Answers1

7

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.

daniel gratzer
  • 11,678
  • 3
  • 46
  • 51
  • 1
    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. –  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 – daniel gratzer 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). –  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 Absolutely. In fact, Clojure provides a function that does just that (with a slightly different interface than I described): [trampoline](http://clojuredocs.org/clojure_core/clojure.core/trampoline). –  Jul 14 '14 at 17:58
  • @delnan: But wouldn't it be possible to use it transparently to implement TCO? I mean: the developer just writes tail calls (without an explicit trampoline) and the compiler uses this technique to optimize them. – Giorgio Jul 15 '14 at 06:32
  • 1
    @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. –  Jul 15 '14 at 06:38