是什么使数据结构递归？

Question

我正在阅读有关递归数据类型的信息 ，该数据类型具有以下引号：

在计算机编程语言中，递归数据类型（也称为递归定义，归纳定义或归纳数据类型）是值的数据类型，该值可能包含相同类型的其他值

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

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

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

Answer 1

但是，这让我真的很困惑，因为固定大小的数组还不包含子数组吗？

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

递归结构（如您提到的链表）实际上包含其自身的版本：

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

而如果您考虑将数组表示为具有元素固定字段的类，则该数组包含elements而不是其他数组：

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中，“向量”的行为本质上与数组相同，在使用它们时可以将其视为数组，但是在内部，它们实际上是一棵树（本质上是多子链表）。