5 ms·

This opinion is totally wild to me. Do you never work with tree data structures? I can't think of a non-trivial program I've written in the past two decades t

This opinion is totally wild to me. Do you never work with tree data structures? I can't think of a non-trivial program I've written in the past two decades that didn't have some recursive tree traversal in it.

Arnavion 3y ago
Tree traversal uses stacks / queues unless you're dealing with a small tree such that you're sure recursion won't blow your stack, or your algorithm can work with tail calls and your language guarantees TCO.
- josephg 3y ago
  Any balanced tree will be shallow enough that this isn't a problem in practice. You'll run out of RAM / hard disk space to store your tree before you run out of stack space.
  - Arnavion 3y ago
    There are lots of trees that can't be balanced, like tries.
mannyv 3y ago
Recursion in production code is bad news, because you can't control the depth of your call tree. At some point you will crash because the runtime won't be able to allocate any more stack. And you can't preflight it because if you could preflight it you wouldn't be doing recursion. Recursion is a nice toy, but in real life it's a ticking time bomb.
- josephg 3y ago
  If you're using some sort of balanced tree (red-black, AVL or a b-tree of some sort), the depth of the tree is guaranteed to be log(n) where n is the number of items. If you recursively descend down the tree, the number of stack frames involved will never exceed the height of the tree. If you have a binary tree with 1 billion elements, the depth will be 20. In a b-tree with a reasonable node width (eg 16), assuming 50% occupancy the depth will be about 8. This is, in practice, totally fine. You won't exhaust your stack traversing a balanced tree.
- munificent 3y ago
  This is just bananas. I work in programming languages. I currently have open in my editor a code formatter that I maintain that uses at least half a dozen recursive algorithms to traverse syntax trees and other data structures. This program is used by almost every user of our language, invoked on every save, and probably executed billions of times a day. Recursion is fine.
  - Joel_Mckay 3y ago
    "Recursion is fine [for your use-case]." In general it is naive, often dangerous, and an inefficient space/time trade-off. I have been writing software for several decades... does that make one less insightful or more biased? https://youtu.be/pmu5sRIizdw?feature=shared&t=31 https://youtu.be/pmu5sRIizdw?feature=shared&t=31 =)
    - munificent 3y ago
      If you're going to make a generalization, I think recursion is fine, efficient, and rarely dangerous. There may be use cases where it's insecure or has performance concerns, but those are the exception. Most of the time, it's fine. We don't generally tell programmers that loops are naive, often dangerous, and risk locking up the program. They certainly can, but most just... don't. Just like loops, recursion can make code much simpler to write, read, and maintain. Every modern language under the sun supports it for very good reasons. Use it.
      - Joel_Mckay 3y ago
        For many reasons, people often add nesting limits in recursive structures to at least constrain how bad they behave when something eventually does go wrong. Parsers are far from immune to these issues. I think we will have to "agree to disagree" here... =)
    - jcgrillo 3y ago
      For a fun time, make a nested json blob about 1000 layers deep[1] and in python: with open('lulz.json') as ayy_lmao: oops = json.load(ayy_lmao) If you parse arbitrary json bytes from the Internet (for example, if you have some public Python API with no auth) then you have given the world a fun little stacktrace generator, and a way to lessen your server room's heating bill. EDIT: btw you can do the same thing in rust's serde_json if the type you're deserializing into somehow supports the nesting, but you'd have to work for it. EDIT2: the only (decent) way I can think to mitigate this in the python app's case is to enforce a sufficiently restrictive Content-Length at the edge, which obviously isn't possible of you expect blobs O(100Kb) uncompressed. Or you could pre-parse to detect nesting. [1] EDIT3: on my machine in ipython right now it's 1485: import json def nest(d): return '{"k":' + str(d) + '}' def make_mess(n): v = 1 for _ in range(n): v = nest(v) return v json.loads(make_mess(1485)) # boom
- naasking 3y ago
  > 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.
klyrs 3y ago
I think there are a lot of web devs here who never do anything more complicated than process data in a loop, and complexity analysis can be accomplished by counting indentation levels. When this viewpoint is applied with a wide brush to all programmers or the whole practice of programming, it results in some pretty spicy takes. On the other hand, recursion extremely expensive in some languages and Python has a notorious limit that forces library writers to roll their own stack. So despite the above, I'm actually in the anti-recursion camp.
- jameshart 3y ago
  There are developers in every field who only work on trivial problems. I bet there are scientific programmers and quants and ML developers who never need more than loops in their work. Loops are powerful tools. But it does you no credit to dismiss ‘web devs’ as more likely to be doing that kind of work. You know the web is full of hierarchies, right? Domain names, the DOM, JSON structures, file directories? And ‘web devs’ build complicated sites with navigation hierarchies and taxonomies and comment threads and team based permissions and complex data visualizations - because web devs build applications that model real world businesses and data all the time, and those things are complex and hierarchical and fractal. Web devs have plenty of uses for recursion. Don’t be dismissive.
  - Joel_Mckay 3y ago
    ML research can be super boring and hard to actually generalize/replicate, but recently became a lucrative field. All commercial projects eventually become "work" when they are no longer fun, and you wouldn't show up unless paid. You also can realize your NDA does not expire on some IP you wrote 15 years ago. lol =)
  - klyrs 3y ago
    I spent several years in the web dev trenches; my opinion is not an out of hand dismissal.
  - DiggyJohnson 3y ago
    Are you arguing against the notion that some branches of programming are going to have to handle complex data structures more often than others? It seems like you're just trying to smooth over a relatively inoffensive point. I don't think most web developers would disagree with GP. You're the one being rude and dismissive of the person you're replying to, frankly.
hehhehaha 3y ago
Tree traversal almost never makes use of tail call recursion. Also, most of the times, you can just use a stack object instead of the program stack which saves you from insane stacktraces, arbitrary stack limits, and a bunch of wasted memory in call frames
Aardwolf 3y ago
> Do you never work with tree data structures? Yes, you can use std::vector or array or similar as a stack, without using recursion (which has some easily reachable depth limit that is much smaller than what your full RAM memory allows, especially in e.g. JS) Of course ideally programming languages would figure out a way to not have this reachable limit and allow as much recursion as your RAM allows... We're still in the ancient world when it comes to this, it seems

Arnavion 3y ago

Tree traversal uses stacks / queues unless you're dealing with a small tree such that you're sure recursion won't blow your stack, or your algorithm can work with tail calls and your language guarantees TCO.

josephg 3y ago
Any balanced tree will be shallow enough that this isn't a problem in practice. You'll run out of RAM / hard disk space to store your tree before you run out of stack space.
- Arnavion 3y ago
  There are lots of trees that can't be balanced, like tries.

mannyv 3y ago

Recursion in production code is bad news, because you can't control the depth of your call tree. At some point you will crash because the runtime won't be able to allocate any more stack. And you can't preflight it because if you could preflight it you wouldn't be doing recursion. Recursion is a nice toy, but in real life it's a ticking time bomb.

josephg 3y ago
If you're using some sort of balanced tree (red-black, AVL or a b-tree of some sort), the depth of the tree is guaranteed to be log(n) where n is the number of items. If you recursively descend down the tree, the number of stack frames involved will never exceed the height of the tree. If you have a binary tree with 1 billion elements, the depth will be 20. In a b-tree with a reasonable node width (eg 16), assuming 50% occupancy the depth will be about 8. This is, in practice, totally fine. You won't exhaust your stack traversing a balanced tree.
munificent 3y ago
This is just bananas. I work in programming languages. I currently have open in my editor a code formatter that I maintain that uses at least half a dozen recursive algorithms to traverse syntax trees and other data structures. This program is used by almost every user of our language, invoked on every save, and probably executed billions of times a day. Recursion is fine.
- Joel_Mckay 3y ago
  "Recursion is fine [for your use-case]." In general it is naive, often dangerous, and an inefficient space/time trade-off. I have been writing software for several decades... does that make one less insightful or more biased? https://youtu.be/pmu5sRIizdw?feature=shared&t=31 https://youtu.be/pmu5sRIizdw?feature=shared&t=31 =)
  - munificent 3y ago
    If you're going to make a generalization, I think recursion is fine, efficient, and rarely dangerous. There may be use cases where it's insecure or has performance concerns, but those are the exception. Most of the time, it's fine. We don't generally tell programmers that loops are naive, often dangerous, and risk locking up the program. They certainly can, but most just... don't. Just like loops, recursion can make code much simpler to write, read, and maintain. Every modern language under the sun supports it for very good reasons. Use it.
    - Joel_Mckay 3y ago
      For many reasons, people often add nesting limits in recursive structures to at least constrain how bad they behave when something eventually does go wrong. Parsers are far from immune to these issues. I think we will have to "agree to disagree" here... =)
  - jcgrillo 3y ago
    For a fun time, make a nested json blob about 1000 layers deep[1] and in python: with open('lulz.json') as ayy_lmao: oops = json.load(ayy_lmao) If you parse arbitrary json bytes from the Internet (for example, if you have some public Python API with no auth) then you have given the world a fun little stacktrace generator, and a way to lessen your server room's heating bill. EDIT: btw you can do the same thing in rust's serde_json if the type you're deserializing into somehow supports the nesting, but you'd have to work for it. EDIT2: the only (decent) way I can think to mitigate this in the python app's case is to enforce a sufficiently restrictive Content-Length at the edge, which obviously isn't possible of you expect blobs O(100Kb) uncompressed. Or you could pre-parse to detect nesting. [1] EDIT3: on my machine in ipython right now it's 1485: import json def nest(d): return '{"k":' + str(d) + '}' def make_mess(n): v = 1 for _ in range(n): v = nest(v) return v json.loads(make_mess(1485)) # boom
naasking 3y ago
> 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.

klyrs 3y ago

I think there are a lot of web devs here who never do anything more complicated than process data in a loop, and complexity analysis can be accomplished by counting indentation levels. When this viewpoint is applied with a wide brush to all programmers or the whole practice of programming, it results in some pretty spicy takes. On the other hand, recursion extremely expensive in some languages and Python has a notorious limit that forces library writers to roll their own stack. So despite the above, I'm actually in the anti-recursion camp.

jameshart 3y ago
There are developers in every field who only work on trivial problems. I bet there are scientific programmers and quants and ML developers who never need more than loops in their work. Loops are powerful tools. But it does you no credit to dismiss ‘web devs’ as more likely to be doing that kind of work. You know the web is full of hierarchies, right? Domain names, the DOM, JSON structures, file directories? And ‘web devs’ build complicated sites with navigation hierarchies and taxonomies and comment threads and team based permissions and complex data visualizations - because web devs build applications that model real world businesses and data all the time, and those things are complex and hierarchical and fractal. Web devs have plenty of uses for recursion. Don’t be dismissive.
- Joel_Mckay 3y ago
  ML research can be super boring and hard to actually generalize/replicate, but recently became a lucrative field. All commercial projects eventually become "work" when they are no longer fun, and you wouldn't show up unless paid. You also can realize your NDA does not expire on some IP you wrote 15 years ago. lol =)
- klyrs 3y ago
  I spent several years in the web dev trenches; my opinion is not an out of hand dismissal.
- DiggyJohnson 3y ago
  Are you arguing against the notion that some branches of programming are going to have to handle complex data structures more often than others? It seems like you're just trying to smooth over a relatively inoffensive point. I don't think most web developers would disagree with GP. You're the one being rude and dismissive of the person you're replying to, frankly.

hehhehaha 3y ago

Tree traversal almost never makes use of tail call recursion. Also, most of the times, you can just use a stack object instead of the program stack which saves you from insane stacktraces, arbitrary stack limits, and a bunch of wasted memory in call frames

Aardwolf 3y ago

> Do you never work with tree data structures? Yes, you can use std::vector or array or similar as a stack, without using recursion (which has some easily reachable depth limit that is much smaller than what your full RAM memory allows, especially in e.g. JS) Of course ideally programming languages would figure out a way to not have this reachable limit and allow as much recursion as your RAM allows... We're still in the ancient world when it comes to this, it seems