3 ms·
Fair point, but how frequently do you see recursive implementations that also pass information to track recursion depth and various other information to limit r
by lmilcin 6y ago
Fair 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.