5 ms·

Recursion is either an abstract way to create a loop or a way to use the call stack as a stack data structure. There isn't really a good reason why it needs to

Recursion is either an abstract way to create a loop or a way to use the call stack as a stack data structure. There isn't really a good reason why it needs to be part of a programmer's toolbox. I think the clever nature of recursion is what has made it into something that some programers think is a better way to traverse a data structure, but I think it is often difficult to justify. Even trees can be traversed with a stack of the current state. If something goes wrong, checking the traversal stack is much easier than a runaway call stack.

skohan 7y ago
While it doesn't find it's way into my everyday programming so often, I think recursion does serve a pedagogic purpose if nothing else. Just like learning a bit of Lisp or Prolog, having the "click" moment when first learning about recursion can be really helpful in building intuitions about programming in general.
tombert 7y ago
I completely disagree. For handling recursive data structures, recursion will lead to shorter, simpler code than trying to hack something together with a loop and a custom stack object. While I agree that some of the more dogmatic FP people acting like recursion is the best thing ever might be a bit overstated, I think it's short-sighted to say that "There isn't really a good reason why it needs to be part of a programmer's toolbox". Not to mention, without using recursion, there's no direct way of dealing with purely immutable data structures. You're going to be stuck creating some kind of mutable reference to serve as a counter to a loop, or to append to a list.
- gallerdude 7y ago
  Finding out how to traverse a tree recursively was one of the first great “aha” moments of learning CS.
  - tombert 7y ago
    About two years ago, I had to (sort of accidentally) create a DSL out of JSON that emitted SQL. My first attempt was trying to hack something together with a bunch of arrays and hashmaps, but I realized that since there's no real "limit" to how nested SQL can be, that that wouldn't work. I scrapped what I was working on, and started over, fully utilizing recursion, and it led to substantially shorter code, that didn't perform measurably slower, and let me handle the full SQL spec correctly. Sadly, I moved off that project, and the person who inherited it didn't understand recursion very well, and rewrote it without recursion, and ended up making it not able to handle the full spec.
  - howard941 7y ago
    Absolutely! As a thought exercise, what sort of non-trivial tree traversal is possible without recursion or looping? I do use recursion quite a bit but always honoring the JPL coding rule (I can't find it) to put some form of safety fusing in recursive code to avoid inadvertent stack blowouts.
    - lincpa 7y ago
      the Pure function pipe data flow completely conforms to the JPL coding rules. [The Pure Function Pipeline Data Flow](https://github.com/linpengcheng/PurefunctionPipelineDataflow https://github.com/linpengcheng/PurefunctionPipelineDataflow)
- BubRoss 7y ago
  But what is a 'recursive' data structure? Recursive describes execution, not data. Data in a tree is a heirarchy. Traversing a tree can be done with a stack, since that's what recursion is doing in a less direct way. Immutable also describes execution and is really just a way of hiding what is really happening under the hood. There isn't anything that recursion enables.
  - tombert 7y ago
    I'm defining "recursive" data structure in basically the same way everyone else does. Here's an example in Haskell: data [a] = [] | a : [a] The element is either empty, or an element and a pointer to another list. This is recursively defined since it points to the source data structure as part of its definition. I know that traversing a tree can be done with a stack/list; I mentioned that in my response, but the code will typically be bigger and less intuitive; if the data structure is recursive (based on my definition from above), it lends itself to a recursive algorithm. Sure, under the hood immutable data might be dressing for something at runtime, but the compiler still needs help to use those features; if I want to loop over something and prepend to a list immutably, at least from a code perspective (not the runtime context), I need recursion to properly respect that.
  - pcstl 7y ago
    A recursive data structure is a data structure that contains a pointer to another instance of itself. Linked lists, trees, etc.
    - Izkata 7y ago
      Since you listed linked lists first, here's a fun little tidbit from my early days: I couldn't understand that until I first understood the recursive structure of binary trees. Only afterwards did I have the realization "ohhh, it's like a tree with only one child at each node" and suddenly understand the recursive structure in linked lists.
  - cgh 7y ago
    Others have described simple recursive data structures, but a real-world example is in the MTOSI definition of network modeling. Equipment Holders (EH), eg slots, can hold Equipment (EQ), eg cards. EHs can also hold other EHs arbitrarily deep, and EQ can hold EQ as well as EHs. So they are mutually recursive. A standard way to walk such data structures is with mutually recursive functions. In other words, a natural way to talk about recursive data structures is with recursive functions and this is made more obvious with data structures that are mutually recursive.
- JustSomeNobody 7y ago
  Remember that not everyone writes code that is designed to run on a machine with lots of RAM. Loops vs Recursion can be a proper engineering trade off when resources are low.
  - tombert 7y ago
    Sure, and I'm not saying you should never write with the loop+stack/list option; right tool, right job. I'm just saying that there are certain jobs that lend themselves to recursion, and one shouldn't discount it as some purely-academic bit of fun; it's a useful tool to have in your arsenal. If you have reason to worry about a stack overflow or something similar, you probably shouldn't be using recursion for that project; if you're working in an environment where you aren't going to realistically hit those restraints (like in my case), recursion is incredibly valuable sometimes. That said, even though I'm somewhat of an FP zealot, I think whenever possible (about 9*% of the time), you should use a looping function like `map`, `filter`, `reduce`, or even the Java-style enhanced-for-loop instead of recursion.
- AKrumbach 7y ago
  I'd be even more specific than that: understanding the transformation to turn a looping function into a recursive one is the key gateway into being able to comprehend code which uses advanced call-stack manipulation patterns, such as continuations or coroutines. While I hesitate to call such methodologies _simpler_ code, such patterns still will certainly yield more maintainable, reliable code in a strict single-thread language such as Javascript.
pcstl 7y ago
It's the opposite, actually - every loop can be trivially encoded as recursion, but loops can't encode many common recursive patterns without a lot of work. Recursion also has the potential to be much clearer than loops in some cases. Of course, there are also cases where one would do much better to not use recursion, but that's why I think people should know of it.
- BubRoss 7y ago
  Recursion just gives you a stack data structure by letting you use the call stack. If you have a stack data structure to use explicitly, then recursion doesn't give you anything and takes away the simplicity of being able to see the entire state of the traversal easily since the call stack and traversal state are now intertwined. You can just take the variables you are passing to each recursive call, put them in a struct, and make a stack of those structs.
  - pcstl 7y ago
    Sure, but depending on the recursion, that technique will vary from "inelegant" to "maddeningly brittle". It seems like going pretty far just to avoid recursion, unless you're in a resource-constrained domain.
    - BubRoss 7y ago
      There is nothing brittle about it, you push values to the stack instead of passing them to a function (which just pushes them to the call stack). It actually ends up being far less brittle in practice because it is much easier to deal with edge cases and errors. You can break out of a loop much easier than returning different values and having those bubble up.

skohan 7y ago

While it doesn't find it's way into my everyday programming so often, I think recursion does serve a pedagogic purpose if nothing else. Just like learning a bit of Lisp or Prolog, having the "click" moment when first learning about recursion can be really helpful in building intuitions about programming in general.

tombert 7y ago

I completely disagree. For handling recursive data structures, recursion will lead to shorter, simpler code than trying to hack something together with a loop and a custom stack object. While I agree that some of the more dogmatic FP people acting like recursion is the best thing ever might be a bit overstated, I think it's short-sighted to say that "There isn't really a good reason why it needs to be part of a programmer's toolbox". Not to mention, without using recursion, there's no direct way of dealing with purely immutable data structures. You're going to be stuck creating some kind of mutable reference to serve as a counter to a loop, or to append to a list.

gallerdude 7y ago
Finding out how to traverse a tree recursively was one of the first great “aha” moments of learning CS.
- tombert 7y ago
  About two years ago, I had to (sort of accidentally) create a DSL out of JSON that emitted SQL. My first attempt was trying to hack something together with a bunch of arrays and hashmaps, but I realized that since there's no real "limit" to how nested SQL can be, that that wouldn't work. I scrapped what I was working on, and started over, fully utilizing recursion, and it led to substantially shorter code, that didn't perform measurably slower, and let me handle the full SQL spec correctly. Sadly, I moved off that project, and the person who inherited it didn't understand recursion very well, and rewrote it without recursion, and ended up making it not able to handle the full spec.
- howard941 7y ago
  Absolutely! As a thought exercise, what sort of non-trivial tree traversal is possible without recursion or looping? I do use recursion quite a bit but always honoring the JPL coding rule (I can't find it) to put some form of safety fusing in recursive code to avoid inadvertent stack blowouts.
  - lincpa 7y ago
    the Pure function pipe data flow completely conforms to the JPL coding rules. [The Pure Function Pipeline Data Flow](https://github.com/linpengcheng/PurefunctionPipelineDataflow https://github.com/linpengcheng/PurefunctionPipelineDataflow)
BubRoss 7y ago
But what is a 'recursive' data structure? Recursive describes execution, not data. Data in a tree is a heirarchy. Traversing a tree can be done with a stack, since that's what recursion is doing in a less direct way. Immutable also describes execution and is really just a way of hiding what is really happening under the hood. There isn't anything that recursion enables.
- tombert 7y ago
  I'm defining "recursive" data structure in basically the same way everyone else does. Here's an example in Haskell: data [a] = [] | a : [a] The element is either empty, or an element and a pointer to another list. This is recursively defined since it points to the source data structure as part of its definition. I know that traversing a tree can be done with a stack/list; I mentioned that in my response, but the code will typically be bigger and less intuitive; if the data structure is recursive (based on my definition from above), it lends itself to a recursive algorithm. Sure, under the hood immutable data might be dressing for something at runtime, but the compiler still needs help to use those features; if I want to loop over something and prepend to a list immutably, at least from a code perspective (not the runtime context), I need recursion to properly respect that.
- pcstl 7y ago
  A recursive data structure is a data structure that contains a pointer to another instance of itself. Linked lists, trees, etc.
  - Izkata 7y ago
    Since you listed linked lists first, here's a fun little tidbit from my early days: I couldn't understand that until I first understood the recursive structure of binary trees. Only afterwards did I have the realization "ohhh, it's like a tree with only one child at each node" and suddenly understand the recursive structure in linked lists.
- cgh 7y ago
  Others have described simple recursive data structures, but a real-world example is in the MTOSI definition of network modeling. Equipment Holders (EH), eg slots, can hold Equipment (EQ), eg cards. EHs can also hold other EHs arbitrarily deep, and EQ can hold EQ as well as EHs. So they are mutually recursive. A standard way to walk such data structures is with mutually recursive functions. In other words, a natural way to talk about recursive data structures is with recursive functions and this is made more obvious with data structures that are mutually recursive.
JustSomeNobody 7y ago
Remember that not everyone writes code that is designed to run on a machine with lots of RAM. Loops vs Recursion can be a proper engineering trade off when resources are low.
- tombert 7y ago
  Sure, and I'm not saying you should never write with the loop+stack/list option; right tool, right job. I'm just saying that there are certain jobs that lend themselves to recursion, and one shouldn't discount it as some purely-academic bit of fun; it's a useful tool to have in your arsenal. If you have reason to worry about a stack overflow or something similar, you probably shouldn't be using recursion for that project; if you're working in an environment where you aren't going to realistically hit those restraints (like in my case), recursion is incredibly valuable sometimes. That said, even though I'm somewhat of an FP zealot, I think whenever possible (about 9*% of the time), you should use a looping function like `map`, `filter`, `reduce`, or even the Java-style enhanced-for-loop instead of recursion.
AKrumbach 7y ago
I'd be even more specific than that: understanding the transformation to turn a looping function into a recursive one is the key gateway into being able to comprehend code which uses advanced call-stack manipulation patterns, such as continuations or coroutines. While I hesitate to call such methodologies _simpler_ code, such patterns still will certainly yield more maintainable, reliable code in a strict single-thread language such as Javascript.

pcstl 7y ago

It's the opposite, actually - every loop can be trivially encoded as recursion, but loops can't encode many common recursive patterns without a lot of work. Recursion also has the potential to be much clearer than loops in some cases. Of course, there are also cases where one would do much better to not use recursion, but that's why I think people should know of it.

BubRoss 7y ago
Recursion just gives you a stack data structure by letting you use the call stack. If you have a stack data structure to use explicitly, then recursion doesn't give you anything and takes away the simplicity of being able to see the entire state of the traversal easily since the call stack and traversal state are now intertwined. You can just take the variables you are passing to each recursive call, put them in a struct, and make a stack of those structs.
- pcstl 7y ago
  Sure, but depending on the recursion, that technique will vary from "inelegant" to "maddeningly brittle". It seems like going pretty far just to avoid recursion, unless you're in a resource-constrained domain.
  - BubRoss 7y ago
    There is nothing brittle about it, you push values to the stack instead of passing them to a function (which just pushes them to the call stack). It actually ends up being far less brittle in practice because it is much easier to deal with edge cases and errors. You can break out of a loop much easier than returning different values and having those bubble up.