3 ms·
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 h
by 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 agoPython 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 agoYou’re right, of course. I had completely forgotten that.
- bjoli 7y agoI 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)