3 ms·

Languages without tail recursion elimination are very annoying. Looking at you JavaScript.

phkahler 12y ago
>> Languages without tail recursion elimination are very annoying. Looking at you JavaScript. Programmers who use tail recursion instead of a loop are very annoying. Looking at you justincormack ;-) Seriously, when I first saw recursion explained using the fibonacci sequence I was really scratching my head. I wondered why anyone would do that. Now that I'm older and wiser, I can see that it's natural to a mathematician. Why anyone who claims to be a programmer or compsci person would do it is beyond me. I suppose it's a simple example, but I'm a fan of introducing concepts with examples that really want the technique in question as a solution.
- emodendroket 12y ago
  How about a depth-first search, then?
  - crimsonalucard 12y ago
    That's not tail recursion! It's tree recursion.
    - emodendroket 12y ago
      Well, good point, but so is the naive implementation of Fibonacci, isn't it?
- toast0 12y ago
  Some languages don't have loops, so you have to use tail recursion. Sometimes, tail recursion is more clear or concise than a loop: Erlang: fib(1) -> 1; fib(2) -> 1; fib(N) when N > 2 -> fib(fib(1), fib(2), N - 2). fib(_A, B, 0) -> B; fib(A, B, N) when N > 0 -> fib(B, A + B, N - 1). C: int fib(int count) { int a = 1, b =1; while (--count >= 2) { int next = a + b; a = b; b = next; } return b; } Notes: Erlang version will crash if given value is less than 1; C version will just return 1 for anything outside of accepted range. Erlang integers become large integers automatically, C integers will overflow. If you prefer fib(0) == 0, you can adjust it, with more work for C, because I cheated the initial conditions/bounds check. (I shrunk the C code a bit more than originally written, and it's now pretty similar in length... I guess it's about the same... which is the point :)
- justincormack 12y ago
  There are excellent uses. State machines as tail recursive functions are great, but in JavaScript you need a trampoline handler, which is much messier.

>> Languages without tail recursion elimination are very annoying. Looking at you JavaScript. Programmers who use tail recursion instead of a loop are very annoying. Looking at you justincormack ;-) Seriously, when I first saw recursion explained using the fibonacci sequence I was really scratching my head. I wondered why anyone would do that. Now that I'm older and wiser, I can see that it's natural to a mathematician. Why anyone who claims to be a programmer or compsci person would do it is beyond me. I suppose it's a simple example, but I'm a fan of introducing concepts with examples that really want the technique in question as a solution.

emodendroket 12y ago
How about a depth-first search, then?
- crimsonalucard 12y ago
  That's not tail recursion! It's tree recursion.
  - emodendroket 12y ago
    Well, good point, but so is the naive implementation of Fibonacci, isn't it?
toast0 12y ago
Some languages don't have loops, so you have to use tail recursion. Sometimes, tail recursion is more clear or concise than a loop: Erlang: fib(1) -> 1; fib(2) -> 1; fib(N) when N > 2 -> fib(fib(1), fib(2), N - 2). fib(_A, B, 0) -> B; fib(A, B, N) when N > 0 -> fib(B, A + B, N - 1). C: int fib(int count) { int a = 1, b =1; while (--count >= 2) { int next = a + b; a = b; b = next; } return b; } Notes: Erlang version will crash if given value is less than 1; C version will just return 1 for anything outside of accepted range. Erlang integers become large integers automatically, C integers will overflow. If you prefer fib(0) == 0, you can adjust it, with more work for C, because I cheated the initial conditions/bounds check. (I shrunk the C code a bit more than originally written, and it's now pretty similar in length... I guess it's about the same... which is the point :)
justincormack 12y ago
There are excellent uses. State machines as tail recursive functions are great, but in JavaScript you need a trampoline handler, which is much messier.