3 ms·

That sounds awfully complicated modifying a recursive algorithm to control the recursion depth. By that, I mean, if sometimes the data happens to be a very deep

That sounds awfully complicated modifying a recursive algorithm to control the recursion depth. By that, I mean, if sometimes the data happens to be a very deep unbalanced tree that would cause a stack overflow with a naive recursive algorithm, you detect that situation and make it work. Isn't that much harder than just using your own stack (from a library/framework)?

munificent 3y ago
> That sounds awfully complicated modifying a recursive algorithm to control the recursion depth. An easy way to do it is to just pass a separate "depth" integer parameter into the recursive function. It then passes that +1 when it makes a recursive call. At the top of the function, if the depth is above your chosen limit, you bail out in some way instead of continuing to recurse. > you detect that situation and make it work. If you really do need to "make it work" for arbitrarily-deeply nested inputs, then you are actually better off using a heap-allocated stack instead of recursion. But in most cases, a recursive implementation will only exceed the stack if the input is malicious or pathological and you can just fail in that case.
- EnigmaFlare 3y ago
  OK, controlling the recursion depth just means failing more gracefully than a stack overflow. The GP's statement that nobody's likely to encounter a bigger problem is silly. It can happen walking a mesh of a 3D model where perfectly valid geometry or ordering might lead to a million-deep branch.
  - naasking 3y ago
    > The GP's statement that nobody's likely to encounter a bigger problem is silly. I didn't actually say that, but even supposing I meant that, walking a 3D mesh in a way that requires you to keep stack context sounds like a pretty unlikely/niche scenario, so it seems even that stronger statement is true.
    - EnigmaFlare 3y ago
      I must have misunderstood your "Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.". It's fairly intuitive to walk a mesh recursively by following adjacent edges and you have to keep track of where you've been which means storing a lot of data somewhere. Maybe there are better algorithms but sometimes you just reach for what's most obvious. I suppose there are many analogous applications of traversing a graph structure.

munificent 3y ago

> That sounds awfully complicated modifying a recursive algorithm to control the recursion depth. An easy way to do it is to just pass a separate "depth" integer parameter into the recursive function. It then passes that +1 when it makes a recursive call. At the top of the function, if the depth is above your chosen limit, you bail out in some way instead of continuing to recurse. > you detect that situation and make it work. If you really do need to "make it work" for arbitrarily-deeply nested inputs, then you are actually better off using a heap-allocated stack instead of recursion. But in most cases, a recursive implementation will only exceed the stack if the input is malicious or pathological and you can just fail in that case.

EnigmaFlare 3y ago
OK, controlling the recursion depth just means failing more gracefully than a stack overflow. The GP's statement that nobody's likely to encounter a bigger problem is silly. It can happen walking a mesh of a 3D model where perfectly valid geometry or ordering might lead to a million-deep branch.
- naasking 3y ago
  > The GP's statement that nobody's likely to encounter a bigger problem is silly. I didn't actually say that, but even supposing I meant that, walking a 3D mesh in a way that requires you to keep stack context sounds like a pretty unlikely/niche scenario, so it seems even that stronger statement is true.
  - EnigmaFlare 3y ago
    I must have misunderstood your "Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.". It's fairly intuitive to walk a mesh recursively by following adjacent edges and you have to keep track of where you've been which means storing a lot of data somewhere. Maybe there are better algorithms but sometimes you just reach for what's most obvious. I suppose there are many analogous applications of traversing a graph structure.