Re:PHP: why GOTO instead of recursion?
by justincormack on Tuesday September 23, 2014 @12:19PM
(#8356109)
Languages without tail recursion elimination are very annoying. Looking at you JavaScript.
[ Parent
| on HN ]
Re:PHP: why GOTO instead of recursion?
by phkahler on Tuesday September 23, 2014 @12:40PM
(#8356258)
>> 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.
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 :)
Re:PHP: why GOTO instead of recursion?
by justincormack on Tuesday September 23, 2014 @02:24PM
(#8357115)
There are excellent uses. State machines as tail recursive functions are great, but in JavaScript you need a trampoline handler, which is much messier.
Re:PHP: why GOTO instead of recursion?
by emodendroket on Tuesday September 23, 2014 @12:58PM
(#8356388)
How about a depth-first search, then?
Re:PHP: why GOTO instead of recursion?
by crimsonalucard on Tuesday September 23, 2014 @01:35PM
(#8356682)
That's not tail recursion! It's tree recursion.
Re:PHP: why GOTO instead of recursion?
by emodendroket on Tuesday September 23, 2014 @02:02PM
(#8356929)
Well, good point, but so is the naive implementation of Fibonacci, isn't it?