On Recursion, Continuations and Trampolines
How is tail recursion different from regular recursion? What do continuations have to do with this, what is CPS, and how do trampolines help? This article provides an introduction, with code samples in Python and Clojure.
Tail recursion is when the recursive call happens in tail position, meaning that it is the last thing the function does before returning its own result. Here's a tail-recursive version of factorial:
The tail call doesn't have to be directly recursive. It can call another function as well, implementing mutual recursion or some more complex scheme. Here's a canonical example of mutual recursion - a silly way to tell whether a number is odd or even:
Both these examples are simple in a way, because they only contain a single call within each function. When functions make multiple calls, things become more challenging. Computing the Fibonacci sequence is a good example:
Here we have two recursive calls to fib_rec within itself. Converting this function to a tail-call variant will be more challenging. How about this attempt:
