4 ms·

> Recursion in production code is bad news, because you can't control the depth of your call tree. Of course you can, if you wanted to, just like you can contr

> Recursion in production code is bad news, because you can't control the depth of your call tree. Of course you can, if you wanted to, just like you can control the iteration count of a loop. It's not even hard. This is simply a non-issue. Some algorithms are much more naturally expressed recursively and writing the imperative equivalent with manual stack handling is just annoying. Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.

Joel_Mckay 3y ago
From my perspective, the main issue it causes (besides flood risks) is an overlapping state dependency that can process-bind large areas of fragmented memory. So, if you try to unroll naive recursive code, than one wins n-many issues instead of 1 predictably separable one. Sure one could pass in a mutex etc., but it is back to using a global again and a single-core bounded context. Best of luck, =)
jcgrillo 3y ago
> This is simply a non-issue. Well, it's about the tradeoffs right? If I have a recursive algorithm that's growing the stack (assuming no TCO, because few languages people actually use in production support it) I'm trading execution time, space, and reliability for economy of expression. In reverse order: - reliability: if, as you suggest, I implement some hard depth limit (which is necessary because all the processes which are running concurrently need to not exceed my max stack depth), and assuming generally that things grow over time (more users, more concurrent processes, more recursive calls needed to get the job done) we face two issues. (1) theres a complicated relationship between the maximum number of concurrent processes and the maximum allowable recursion depth. Getting it wrong could crash the entire program! If this is a web server that's means we just killed a whole bunch of connections all at once. (2) eventually, over time, we'll need to raise the recursion limit, which entails rebalancing the concurrency limit. Hard walls like this are bad news in systems. If instead this was implemented iteratively the system would degrade softly as the iteration count grows--each process would take longer to complete, but they'd still all complete. Assuming I'm monitoring process execution time I can predict and respond to this proactively instead of being faced with an emergency where the system is just completely broken. - space: this is obvious I guess, more stack frames == more memory. The problem is worse in some languages than others. - time: this may be less obvious, and there may be optimizations which render it false, but generally in my experience iterative code gets pipelined better and runs quicker. > Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter. I guess that depends on the situation. I've encountered hard walls and performance issues from recursion enough times in my career thus far that I make the extra effort to avoid it. I could totally see the value, though, in areas where you know ahead of time how the recursion depth will scale over time. More often than not, though, that's unknowable at implementation time so better err on the side of caution. EDIT: upon re-reading this I think it might have been clearer if I insted wrote "task" every time I wrote "process"--I'm not talking specifically about any OS feature.
- furyofantares 3y ago
  They were referring to algorithms that need to use that much space either way and where the alternative is maintaining your own stack.
  - jcgrillo 3y ago
    Even in that case there's a tradeoff, if that stack needs to be large you can maintain it on the heap. Now you can do that to some extent with either a recursive implementation or not of course, but it's still a matter of deciding which is the better approach. It's not simply the case that "you can always just use recursion and it'll be totally fine mostly".
- naasking 3y ago
  I think you're overthinking it. Here are probably the people who need to worry about recursion depth: embedded developers working with limited memory, and developers working on data systems that process huge data sets (and even this is debatable as stack growth is log n with these tree data structures). My process for deciding when to use iteration or recursion is simple: if each step needs to keep context then use recursion, otherwise use iteration (unless recursion with TCO is the native idiom of course). I've never had an issue that wasn't an obvious bug that iteration would have somehow solved. If any bug that terminated a thread was fatal to the whole process then I suggest the thread termination handler should handle this more gracefully. Increased space usage is a non-issue IMO. Translating a stack frame to a data structure you manage as an explicit stack requires the same space within a small constant factor. And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.
  - jcgrillo 3y ago
    > I think you're overthinking it Quite likely :) > And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion. This is a very good point. Alright, you've convinced me to start playing with recursion again. Just not in java or python.
EnigmaFlare 3y ago
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.
      - 3y ago

Joel_Mckay 3y ago

From my perspective, the main issue it causes (besides flood risks) is an overlapping state dependency that can process-bind large areas of fragmented memory. So, if you try to unroll naive recursive code, than one wins n-many issues instead of 1 predictably separable one. Sure one could pass in a mutex etc., but it is back to using a global again and a single-core bounded context. Best of luck, =)

jcgrillo 3y ago

> This is simply a non-issue. Well, it's about the tradeoffs right? If I have a recursive algorithm that's growing the stack (assuming no TCO, because few languages people actually use in production support it) I'm trading execution time, space, and reliability for economy of expression. In reverse order: - reliability: if, as you suggest, I implement some hard depth limit (which is necessary because all the processes which are running concurrently need to not exceed my max stack depth), and assuming generally that things grow over time (more users, more concurrent processes, more recursive calls needed to get the job done) we face two issues. (1) theres a complicated relationship between the maximum number of concurrent processes and the maximum allowable recursion depth. Getting it wrong could crash the entire program! If this is a web server that's means we just killed a whole bunch of connections all at once. (2) eventually, over time, we'll need to raise the recursion limit, which entails rebalancing the concurrency limit. Hard walls like this are bad news in systems. If instead this was implemented iteratively the system would degrade softly as the iteration count grows--each process would take longer to complete, but they'd still all complete. Assuming I'm monitoring process execution time I can predict and respond to this proactively instead of being faced with an emergency where the system is just completely broken. - space: this is obvious I guess, more stack frames == more memory. The problem is worse in some languages than others. - time: this may be less obvious, and there may be optimizations which render it false, but generally in my experience iterative code gets pipelined better and runs quicker. > Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter. I guess that depends on the situation. I've encountered hard walls and performance issues from recursion enough times in my career thus far that I make the extra effort to avoid it. I could totally see the value, though, in areas where you know ahead of time how the recursion depth will scale over time. More often than not, though, that's unknowable at implementation time so better err on the side of caution. EDIT: upon re-reading this I think it might have been clearer if I insted wrote "task" every time I wrote "process"--I'm not talking specifically about any OS feature.

furyofantares 3y ago
They were referring to algorithms that need to use that much space either way and where the alternative is maintaining your own stack.
- jcgrillo 3y ago
  Even in that case there's a tradeoff, if that stack needs to be large you can maintain it on the heap. Now you can do that to some extent with either a recursive implementation or not of course, but it's still a matter of deciding which is the better approach. It's not simply the case that "you can always just use recursion and it'll be totally fine mostly".
naasking 3y ago
I think you're overthinking it. Here are probably the people who need to worry about recursion depth: embedded developers working with limited memory, and developers working on data systems that process huge data sets (and even this is debatable as stack growth is log n with these tree data structures). My process for deciding when to use iteration or recursion is simple: if each step needs to keep context then use recursion, otherwise use iteration (unless recursion with TCO is the native idiom of course). I've never had an issue that wasn't an obvious bug that iteration would have somehow solved. If any bug that terminated a thread was fatal to the whole process then I suggest the thread termination handler should handle this more gracefully. Increased space usage is a non-issue IMO. Translating a stack frame to a data structure you manage as an explicit stack requires the same space within a small constant factor. And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.
- jcgrillo 3y ago
  > I think you're overthinking it Quite likely :) > And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion. This is a very good point. Alright, you've convinced me to start playing with recursion again. Just not in java or python.

EnigmaFlare 3y ago

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.
    - 3y ago