6 ms·
It's the opposite, actually - every loop can be trivially encoded as recursion, but loops can't encode many common recursive patterns without a lot of work. Re
by pcstl 7y ago
It's the opposite, actually - every loop can be trivially encoded as recursion, but loops can't encode many common recursive patterns without a lot of work.
Recursion also has the potential to be much clearer than loops in some cases.
Of course, there are also cases where one would do much better to not use recursion, but that's why I think people should know of it.
- BubRoss 7y agoRecursion 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.