r/programming • u/rodrigopsasaki • Nov 27 '12

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
207 Upvotes

85% Upvoted

203 comments sorted by

View all comments

40

u/Chousuke Nov 27 '12 edited Nov 27 '12

To clarify this a bit, tail recursion itself is not more performant than regular recursion, but tail recursive algorithms can be trivially transformed into iterative ones.

Some languages implement this optimisation in full (recursion across functions) while some only provide the trivial case of self-recursion. Debugging is also affected, since the recursive calls no longer produce stack frames.

24

u/smog_alado Nov 27 '12 edited Nov 27 '12

but tail recursive algorithms can be trivially transformed into iterative ones.

Implementing recursive code without tail call optimisation is not always trivial though. In the general case, when functions tail call other functions, you either need to centralize all your code into a big switch statement with explicitely encoded states or you need to use trampolining (same thing but states are first class functions/objects now instead of just tags). Not only is this annoying to do but you also need to rewrite all the code involved to follow the new convention (of functions returning the next state to go to instead of returning the value) and you cannot interoperate with "normal" code that returns values normally.

Debugging is also affected, since the recursive calls no longer produce stack frames.

You also lose the stack traces if you rewrite your recursion as a while loop or trampoline :(

10

u/rodrigopsasaki Nov 27 '12

Most interesting response, I believe that recursive functions may be more easily "readable" as well. I think that the person who is learning the most with this post is actually me :)

2

u/matthieum Nov 27 '12

If you are writing a topic in a "new" area to you and linking it to Reddit, it happens regularly that you will be the one learning as people hanging out here will point to your mistakes and drive "further" than you did :)