是什么使数据结构递归? [英] What makes a data structure recursive?

问题描述

我正在阅读有关递归数据类型，该引用具有以下引号:

I was reading about Recursive Data Type which has the following quote:

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

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

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

I understand that Linked List and Trees can be recursive data type because it contains smaller version of the same data structure, like a Tree can have a subtree.

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

However, it go me really confused because isn't fixed size array also contains sub-array? which is still the same type?

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

Can someone explain with examples that what makes a data structure recursive?

推荐答案

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

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

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

Conceptually, you could say that every array "contains" sub-arrays, but the arrays themselves aren't made up of smaller arrays in the code. An array is made up of a continuous chunk of elements, not other arrays.

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

A recursive structure (like, as you mentioned, a linked list), literally contains versions of itself:

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

如果您想到的是一个表示为具有固定元素字段的类的数组，则该数组包含 elements ，而不包含其他数组:

Whereas, if you think of an array represented as a class with fixed fields for elements, it contains elements, not other arrays:

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

(这是一个不好的，不准确的数组表示形式，但这是我可以用简单的代码进行交流的最好方法.)

(This is a bad, inaccurate representation of an array, but it's the best I can communicate in simple code).

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

A structure is recursive if while navigating through it, you come across "smaller" versions of the whole structure. While navigating through an array, you'll only come across the elements that the array holds, not smaller arrays.

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

Note though, that this depends entirely on the implementation of the structure. In Clojure for example, "vectors" behave essentially identical to arrays, and can be thought of as arrays while using them, but internally, they're actually a tree (essentially a multi-child linked list).

这篇关于是什么使数据结构递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！