recursion - 是什么让数据结构递归？

Question

我正在阅读有关 Recursive Data Type 的内容其中有以下引用:

In computer programming languages, a recursive data type (also known as a recursively-defined, inductively-defined or inductive data type) is a data type for values that may contain other values of the same type

我知道链表和树可以是递归数据类型，因为它包含相同数据结构的较小版本，就像树可以有子树一样。

但是，这让我真的很困惑，因为固定大小的数组不是也包含子数组吗？哪个仍然是同一类型？

有人可以举例说明什么使数据结构递归吗？

Answer 1

However, it go me really confused because isn't fixed size array also contains sub-array?

从概念上讲，您可以说每个数组“包含”子数组，但数组本身并不是由代码中较小的数组组成。数组由连续的元素 block 组成，而不是其他数组。

递归结构(如您提到的，链表)实际上包含其自身的版本:

class Node {
    Node head = null; // <-- Nodes can literally hold other Nodes
}

然而，如果您将数组视为具有元素固定字段的类，那么它包含元素，而不是其他数组:

class Array<E> {
   E elem1 = ...; // <-- In the code, an array isn't made up of other arrays,
   E elem2 = ...; //      it's made up of elements.
    ...
}

(这是一个糟糕的、不准确的数组表示，但它是我可以用简单代码进行通信的最佳表示)。

如果在浏览结构时遇到整个结构的“较小”版本，则该结构是递归的。在数组中导航时，您只会遇到该数组包含的元素，而不是较小的数组。

但请注意，这完全取决于结构的实现。例如，在 Clojure 中，“向量”的行为本质上与数组相同，并且在使用它们时可以将其视为数组，但在内部，它们实际上是一棵树(本质上是一个多子链表)。