4 ms·
Recursion just gives you a stack data structure by letting you use the call stack. If you have a stack data structure to use explicitly, then recursion doesn't
by BubRoss 7y ago
Recursion just gives you a stack data structure by letting you use the call stack. If you have a stack data structure to use explicitly, then recursion doesn't give you anything and takes away the simplicity of being able to see the entire state of the traversal easily since the call stack and traversal state are now intertwined.
You can just take the variables you are passing to each recursive call, put them in a struct, and make a stack of those structs.
- pcstl 7y agoSure, but depending on the recursion, that technique will vary from "inelegant" to "maddeningly brittle". It seems like going pretty far just to avoid recursion, unless you're in a resource-constrained domain.
- BubRoss 7y agoThere is nothing brittle about it, you push values to the stack instead of passing them to a function (which just pushes them to the call stack). It actually ends up being far less brittle in practice because it is much easier to deal with edge cases and errors. You can break out of a loop much easier than returning different values and having those bubble up.