3 ms·

Tail Recursion

• simendsjo 7y ago
  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.
• bjoli 7y ago
  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.
  • klmr 7y ago
    (nonsense deleted)
    • kd5bjo 7y ago
      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.
      • klmr 7y ago
        You’re right, of course. I had completely forgotten that.
    • bjoli 7y ago
      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)
• BlackLotus89 7y ago
  https://www.youtube.com/watch?v=-PX0BV9hGZY https://www.youtube.com/watch?v=-PX0BV9hGZY for anyone who doesn't know it already
• lispm 7y ago
  > 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.pdf https://dspace.mit.edu/bitstream/handle/1721.1/5790/AIM-353....
• oefrha 7y ago
  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 https://stackoverflow.com/a/18506625
  • klmr 7y ago
    > 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.
    • oefrha 7y ago
      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.