7 ms·

Outside of a university course, if I see recursion in a non-FP language I consider it a code-smell

mikepurvis 2y ago
The only time I ever do it is for tree walking, and then it's always a private internal function, so like: def process_that_tree(my_tree): def _handle(node): # do the things for child in node.children: _handle(child) _handle(my_tree.root) The processing can even be brought outside sometimes, or the walker can just become a generator, yielding nodes out to a regular loop doing the actual work. Either way, the recursive part is kept very minimal and easy to reason about. Obviously for the filesystem these kinds of abstractions exist already in shutil/pathlib/glob, but it still can have a place for dealing with other kinds of hierarchies, like a package dependency tree or the like.
II2II 2y ago
While I am not a fan of recursion, the call stack that enables it sounds infinitely better than statically allocating space for parameters and return values. Besides, it makes some algorithms clearer. That is certainly useful in learning environments, including early academic research.
- Joel_Mckay 2y ago
  Depends on the CPU, in some architectures the stack pointers had low finite capacity before overflowing.
munificent 2y ago
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 2y 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 2y 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 2y ago
      There are lots of trees that can't be balanced, like tries.
- mannyv 2y 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 2y 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 2y 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.
nerpderp82 2y ago
Recursion is like an inductive proof, you can show it is correct and it normally fits on half of a small screen.
- Joel_Mckay 2y ago
  There is an argument that all recursive proofs can be made iterative due to isomorphism. You are not lazy enough to be a good programmer yet. ;-)
  - nerpderp82 2y ago
    Yeah, but that is error prone and more complex. A compiler can make those same transformations. I'd argue that the properly lazy programmer is the one using recursion. To get even lazier, one should move into relational algebra.
    - Joel_Mckay 2y ago
      Meh, or just choose a documented data structure that supports your problem scope. If it takes longer than 1 coffee, than someone is usually approaching things the wrong way... Have to think "minimum effort" here... ;-)
      - nerpderp82 2y ago
        I have seen 150 lines of SQL replaced with 12k lines of Java.
        Joel_Mckay 2y ago
        Only 12k lines? That is efficient for most Java programmers. =)
        nerpderp82 2y ago
        Thank you! :)

The only time I ever do it is for tree walking, and then it's always a private internal function, so like: def process_that_tree(my_tree): def _handle(node): # do the things for child in node.children: _handle(child) _handle(my_tree.root) The processing can even be brought outside sometimes, or the walker can just become a generator, yielding nodes out to a regular loop doing the actual work. Either way, the recursive part is kept very minimal and easy to reason about. Obviously for the filesystem these kinds of abstractions exist already in shutil/pathlib/glob, but it still can have a place for dealing with other kinds of hierarchies, like a package dependency tree or the like.

II2II 2y ago

While I am not a fan of recursion, the call stack that enables it sounds infinitely better than statically allocating space for parameters and return values. Besides, it makes some algorithms clearer. That is certainly useful in learning environments, including early academic research.

Joel_Mckay 2y ago
Depends on the CPU, in some architectures the stack pointers had low finite capacity before overflowing.

munificent 2y ago

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 2y 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 2y 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 2y ago
    There are lots of trees that can't be balanced, like tries.
mannyv 2y 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 2y 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 2y 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.

nerpderp82 2y ago

Recursion is like an inductive proof, you can show it is correct and it normally fits on half of a small screen.

Joel_Mckay 2y ago
There is an argument that all recursive proofs can be made iterative due to isomorphism. You are not lazy enough to be a good programmer yet. ;-)
- nerpderp82 2y ago
  Yeah, but that is error prone and more complex. A compiler can make those same transformations. I'd argue that the properly lazy programmer is the one using recursion. To get even lazier, one should move into relational algebra.
  - Joel_Mckay 2y ago
    Meh, or just choose a documented data structure that supports your problem scope. If it takes longer than 1 coffee, than someone is usually approaching things the wrong way... Have to think "minimum effort" here... ;-)
    - nerpderp82 2y ago
      I have seen 150 lines of SQL replaced with 12k lines of Java.
      - Joel_Mckay 2y ago
        Only 12k lines? That is efficient for most Java programmers. =)
        nerpderp82 2y ago
        Thank you! :)