3 ms·

If you are used to Lisp-like constructs, tail recursion can give solutions that are both idiomatic and efficient. [0] https://en.wikipedia.org/wiki/Tail_call h

• ncmncm 5y ago
  I.e., the compiler converts the recursive code you wrote into the iterative form you could have written, and runs that instead because it's faster.
  • Jtsummers 5y ago
    I find this argument interesting because, to me, it leads to endorsing a view that we should be using goto and conditional jumps instead of for/while loops and similar structured programming elements. I mean, the former are more explicit, the latter implicit, since the compiler converts the latter into the former. Having maintained a fair amount of unstructured code, I'd rather stick with the higher level languages since they allow me to express my intent more clearly. Which pushes me to using recursion where it's appropriate and the language has appropriate facilities to handle tail call elimination.
    • ncmncm 5y ago
      We make languages and compilers the way we do for reasons. But it is a mistake to confuse what automation hides from you, for practical reasons, with fundamental qualities of the universe or of computation. Another common example of the error is describing an algorithm as N log N, assuming that the numbers involved occupy constant space and multiply in constant time. In real-world computation, space tends to log N, and multiply in close to (log N)^2 time and power consumption. We get away with it for the same reason recursion works: the problems we apply our algorithms to usually fit in conveniently constrained space, and our multiplier hardware takes the same time and power for small numbers as for the biggest ones we can conveniently represent.