A nice and clear explanation of why tail recursion is necessary and how it works. I usually don't like mathy examples, but it worked fine here. I especially liked the section on trampolines as I didn't know how transpilers usually did that. Well worth the read.
Recursion is the fundamental looping facility. Every kind of loop can be translated to recursion. That's why I think all languages that should be compiled to has it.
Translating one looping facility to another is usually very painful. Translating a looping facility to recursion is less painful :)
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.
Python for loops aren’t actually bounded: if the iterator you’re looping over doesn’t terminate then neither will the loop. It also only calls the iterator’s next() method once per loop, so it’s possible for the body of a loop to affect future iterations by mutating the iterator.
I saw this before you deleted it, and i just wanted to say that I would much rather compile to tail recursion than a while loop, but I generally try to avoid explicit mutation (being a scheme guy)
> 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.
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't need to recognize that it is a case of recursion or a loop. Tail call optimization (TCO) is the more general form.
See Scheme from 1976:
LAMBDA, The Ultimate Imperative, by Guy Lewis Steele Jr. and Gerald Jay Sussman, MIT AI Memo 353
Small correction: this answer does not use the Y combinator to optimise tail recursion in Python (and this would be impossible). Instead, it modifies the Y combinator to do this, by using an iterative loop in its implementation.
11 comments
[ 2.8 ms ] story [ 35.3 ms ] threadTranslating one looping facility to another is usually very painful. Translating a looping facility to recursion is less painful :)
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.
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't need to recognize that it is a case of recursion or a loop. Tail call optimization (TCO) is the more general form.
See Scheme from 1976:
LAMBDA, The Ultimate Imperative, by Guy Lewis Steele Jr. and Gerald Jay Sussman, MIT AI Memo 353
https://dspace.mit.edu/bitstream/handle/1721.1/5790/AIM-353....
[1] https://stackoverflow.com/a/18506625
Small correction: this answer does not use the Y combinator to optimise tail recursion in Python (and this would be impossible). Instead, it modifies the Y combinator to do this, by using an iterative loop in its implementation.