什么使数据结构递归?

问题描述

我正在阅读有关 递归数据类型 的内容，其中引用了以下内容:

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

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

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

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?

推荐答案

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

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
}

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

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

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