3 ms·
You’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
by Jtsummers 6y ago
You’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]