3 ms·
Recursion with a tail call and iteration are the same, though. The difference between tail recursion and iteration is whether or not the target of a jump happen
by barrkel 17y ago
Recursion with a tail call and iteration are the same, though. The difference between tail recursion and iteration is whether or not the target of a jump happens to be the start of a function or not.
- bad_user 17y ago> Recursion with a tail call and iteration are the same, though. No they aren't. Maybe for self-recursive functions, but you're stretching it. > The difference between tail recursion and iteration is whether or not the target of a jump happens to be the start of a function or not. That's the difference between a subroutine and a coroutine. Yeah, having coroutines implies you have subroutines as well, but the reverse is not true.
- nostrademons 17y agoThey'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).