Tail Recursion | Hacker News Reader

Tail Recursion

functional.christmas

29 pointsbendiksolheim11 comments

> 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

https://dspace.mit.edu/bitstream/handle/1721.1/5790/AIM-353....

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.

(nonsense deleted)

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.

You’re right, of course. I had completely forgotten that.

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)

https://www.youtube.com/watch?v=-PX0BV9hGZY for anyone who doesn't know it already

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.

This Stack Overflow answer[1] presents an interesting way to do tail call optimization in Python using the Y combinator.

[1] https://stackoverflow.com/a/18506625

> tail recursion in Python using the Y combinator

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.

Yes, I wasn’t very precise with my wording, and you seem to have responded to an even more imprecise version of my comment which I immediately edited.

Reply on news.ycombinator.com