3 ms·

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,

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.

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.