什么使数据结构递归？

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

数据类型描述了数据如何存储（至少在逻辑上是这样；在较深的层上，无论如何只有数字、位、晶体管等）。虽然一个数组（但只是一个非空数组）可以被认为是加上另一个（子）数组（这种方法通常用于 Lisp 和 Prolog 等语言中的列表），但它通常按元素存储。

例如，Prolog 中的列表被定义为一个空列表（一种特殊情况）或一个元素（称为 head）与另一个列表（称为 tail）连接。这构成了递归数据类型。

另一方面，C 中的列表可以定义为struct list { char[100] data; int length; }。这里 list 未用于定义 list 的方式（仅使用 char[] 和 int），因此它不是递归数据类型。

Answer 2

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

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

一个递归结构（就像你提到的，一个链表），字面上包含它自己的版本：

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

然而，如果您认为一个数组表示为具有固定元素字段的 class，它包含 个元素 ，而不是其他数组：

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.
    ...
}

（这是一个糟糕的、不准确的数组表示，但它是我能用简单的代码交流的最好的）。

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

不过请注意，这完全取决于结构的实现。例如，在 Clojure 中，"vectors" 的行为本质上与数组相同，在使用它们时可以将其视为数组，但在内部，它们实际上是一棵树（本质上是一个多子链表）。

什么使数据结构递归？

What makes a data structure recursive?

tree

recursion

linked-list

graph-algorithm