Re:Thinking About Recursion
by vertex-four on Wednesday March 08, 2017 @07:44PM
(#13825581)
Indeed. People who claim recursion is the only way to handle some types of data structures are missing how recursion is implemented. In practice, it boils down to a stack and a loop - and in the case of tail-recursive functions, not even the stack - though it may be a little prettier if you use recursion.
[ Parent
| on HN ]
Re:Thinking About Recursion
by charles-salvia on Wednesday March 08, 2017 @09:06PM
(#13826227)
Recursion sometimes makes it easier to implement certain algorithms, since modern programming languages have an implicit call stack which conveniently provides a snapshot of the state of all local stack variables at that point in the algorithm.
Re:Thinking About Recursion
by crimsonalucard on Thursday March 09, 2017 @01:41AM
(#13827515)
Here's a mind bending thought. It is actually the loop that is syntactic sugar and recursion is the implementation.
You're begging the question of what the lambda calculus is. As a theoretical basis for computing it sits equivalently with Turing machines. In practical use, there are consequences with trying to represent the computation with one or the other model, and our physical hardware resembles neither, really.
Re:Thinking About Recursion
by vertex-four on Thursday March 09, 2017 @06:13AM
(#13828520)
In practice, lambda calculus machines are rare, and your code probably compiles down to machine code that more closely emulates a loop and a stack. I'm not saying they're not theoretically equivalent, of course.