4 ms·
They're the same in terms of what the machine is doing, assuming your compiler does tail-call optimization. That's not the same as being "the same" - they pres
by nostrademons 17y ago
They're the same in terms of what the machine is doing, assuming your compiler does tail-call optimization. That's not the same as being "the same" - they present a very different abstraction to the programmer. That was the point of my analogy.
You can see this difference by looking at one of the ways this abstraction leaks. Consider stack traces. In a sane language, you expect an error to give you a stack trace of functions that have been called. If you treat recursion as iteration, then either you'll have to omit some function calls from the stack, or your algorithm won't work in constant space anymore. Either violates some expectations of the programmer.
I also said "recursion" and not "tail recursion". There are some algorithms that are impossible to implement without an external stack under iteration (eg. tree traversal), and others where you need to use iteration because a stack is not appropriate (eg. breadth-first search).