Tail Recursion

&gt; Tail recursion is a special way of writing recursive functions such that a compiler can optimize the recursion away and implement the algorithm as a loop instead.<p>Typically I think more like this: a compiler will compile the tail call into a jump-like construct. Tail recursion is then just only one application of this. The compiler won&#x27;t need to recognize that it is a case of recursion or a loop. Tail call optimization (TCO) is the more general form.<p>See Scheme from 1976:<p>LAMBDA, The Ultimate Imperative, by Guy Lewis Steele Jr. and Gerald Jay Sussman, MIT AI Memo 353<p><a href="https:&#x2F;&#x2F;dspace.mit.edu&#x2F;bitstream&#x2F;handle&#x2F;1721.1&#x2F;5790&#x2F;AIM-353.pdf" rel="nofollow">https:&#x2F;&#x2F;dspace.mit.edu&#x2F;bitstream&#x2F;handle&#x2F;1721.1&#x2F;5790&#x2F;AIM-353....</a>

Recursion is the fundamental looping facility. Every kind of loop can be translated to recursion. That&#x27;s why I think all languages that should be compiled to has it.<p>Translating one looping facility to another is usually very painful. Translating a looping facility to recursion is less painful :)<p>Edit: as an exanple: try compiling the common lisp loop macro to python for loops. I am not even sure it is possible. Compiling it to recursive functions (of which python lacks the tail recursion optimized kind) is however a pretty straightforward, but still very much nontrivial, problem.

<a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=-PX0BV9hGZY" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=-PX0BV9hGZY</a> for anyone who doesn&#x27;t know it already

A nice and clear explanation of why tail recursion is necessary and how it works. I usually don&#x27;t like mathy examples, but it worked fine here. I especially liked the section on trampolines as I didn&#x27;t know how transpilers usually did that. Well worth the read.

This Stack Overflow answer[1] presents an interesting way to do tail call optimization in Python using the Y combinator.<p>[1] <a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;18506625" rel="nofollow">https:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;18506625</a>