3 ms·
It's not recursive. To be recursive you'd have to be able to unwind some sort of memory to get all previous states.
by Gordonjcp 4y ago
It's not recursive. To be recursive you'd have to be able to unwind some sort of memory to get all previous states.
- viraptor 4y agoI don't think that's required for recursion. You only need access to as many previous states as you need for the result, but not all. We often talk about tail recursion optimisation where the stack never grows.
- dustingetz 4y agothe unwinding property comes from the stack; see tail recursion
- fnordpiglet 4y agoYou can implement binary search recursively, which doesn’t care about the stack just the final iteration. I don’t see where the stack unwinding is necessarily for “call the same function inside itself unless you’re done” except in cases where the stack is used to compute a final answer that’s based on the prior iterations. Maybe it’s fair to say those would best be implemented iteratively, but it’s unnecessary that they be.