4 ms·
None of the above actually require recursion. Some of the above problems have very neat recursive solution but the recursion is bad idea as it tends to various
by lmilcin 6y ago
None of the above actually require recursion.
Some of the above problems have very neat recursive solution but the recursion is bad idea as it tends to various edge cases.
For example, "write a parser for a file format that contains arbitarily nested data strucutres", is exactly a problem where you DO NOT want to use recursion, and the reason is that "arbitarily" part. What if there is 1000 levels? What if there is 100 thousand levels?
DoS guys love these kinds of implementations. Just send very small, very well compressed payload and look how it all crashes and burns.
- Jtsummers 6y agoYou’d run into the same denial of service problem in an iterative solution with an explicit stack/data structure that can be grown arbitrarily as well. The only way to prevent such an attack is an explicit limit (perhaps calculated at run time based on system specs) which can be done with either a recursive or iterative implementation but requires deliberate awareness either way.
- lmilcin 6y agoFair point, but how frequently do you see recursive implementations that also pass information to track recursion depth and various other information to limit resource usage? Have you ever seen a recursive call that also tries to detect/break cycles in the data structure? I suspect the reason these things get left out the moment the developer decides on a recursive function is because it doesn't look nearly as much elegant then.
- kazinator 6y agoDepth is just an extra parameter d, which you pass to the recursive calls as d + 1. This is still elegant compared to tracking depth in a non-recursive solution. When you add this parameter to a recursive solution that is lacking it, your compiler will flag all the places where you are neglecting to pass it, and you just copy and paste d + 1 into those places. Or at worst, it will be caught as a run-ime insufficient parameters error. At the end of this exercise, you not only have working code, but an inductive proof that d has the correct value everywhere. There are no cases where the depth is mismanaged, as could happen in some iterative solution where you must insert assignments to d, that do not create any sort of error when they are missing.
- deleted 6y ago[deleted]
- pksebben 6y ago:(){ :|:& };:
- hydroxideOH- 6y agoRecursion doesn't use more space than iteration in languages with tail call optimization
- lmilcin 6y agoThat's false. You would be correct if you wrote "Tail-optimizable recursion doesn't use more space than iteration in languages with tail call optimization"
- hydroxideOH- 6y agoYou're right, that's what I meant.
- kazinator 6y agoI would say, DoS people love these kinds of specifications. I would specify the data structure is ostensibly arbitrary, but conforming implementations can diagnose and reject more than 64 levels of nesting. Anything needing more than 64 levels of nesting can safely be assumed to be DoS.