Get the latest tech news
Recursion, continuations and trampolines (2017)
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. Recursion and Tail Recursion Here's a textbook version of a recursive factorial implementation in Python: def fact_rec(n): if n == 0: return 1 else: return n * fact_rec(n - 1) 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.
This is getting beyond the scope of the article, but when unbounded continuations can be treated as first-class values in a language, they become so powerful that they can be used to implement pretty much any control-flow feature you can imagine - exceptions, threads, coroutines and so on. For the factorial, we used an extra parameter to get a tail-call version; for Fibonacci we needed two; for more advanced examples (like merge sort) it wasn't very clear how to do the conversion. To overcome this, the recommended programming style in Clojure is explicit loop...recur iteration, which makes tail-recursive algorithms relatively easy (and efficient) to express.
Or read this on Hacker News