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?

Improve this question
1
  • 1
    When you say "conceal" what do you mean? Like hiding the fact that you've created helper functions with different signatures?
    – Sean McSomething
    CommentedOct 22, 2013 at 19:48

1 Answer 1

Reset to default
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.

Improve this answer
7
  • 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.
    – user7043
    CommentedOct 22, 2013 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
    CommentedOct 22, 2013 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).
    – user7043
    CommentedOct 22, 2013 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
    CommentedJul 14, 2014 at 17:16
  • 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.
    – user7043
    CommentedJul 15, 2014 at 6:38

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.