结构递归与生成递归有何不同？ [英] How does structural recursion differ from generative recursion?

问题描述

维基百科中的生成递归描述很清楚，但是我对结构递归的概念感到困惑。

The description of generative recursion in Wikipedia is clear to me, but I'm confused about the concept of structural recursion.

有人可以解释一下计算第n个斐波那契数的函数和计算从1到N的阶乘的函数是否是结构性的或

Can someone explain if a function calculating nth Fibonacci number and a function calculating factorial from 1 to N will be structural or generative?

推荐答案

结构递归和生成递归之间的主要区别在于递归过程从何处获取其起作用的数据以及如何使用它处理该数据。具体来说，对于结构递归，对原始输入数据的子集进行递归调用。对于生成递归，将对从原始输入数据构造/计算的数据进行递归调用。

The key difference between structural and generative recursion is where a recursive procedure gets the data that it works on and how it processes that data. Specifically, for structural recursion, a recursive call is made on a subset of the original input data. Whereas for generative recursion, a recursive call is made on data that was constructed/calculated from the original input data.

例如，如果要计算元素数在链接列表中，您可以执行以下操作：

For example, if you wanted to count the number of elements in a linked list, you could do the following:

int NumberOfNodes(ListNode* node) {
    if (node == nullptr) return 0;
    return 1 + NumberOfNodes(node->next);
}

在这里，递归调用 NumberOfNodes 在 node-> next 上进行，这是已经存在的原始输入的一部分。在这种情况下，递归的工作方式是将输入分解为较小的部分，然后对较小的部分进行递归。

Here, the recursive call to NumberOfNodes is being made on node->next, which is a piece of the original input which already existed. In this case, the recursion works by breaking down the input into smaller pieces, then recursing on the smaller pieces.

同样，此代码在BST中搜索值是结构性递归，因为递归调用是对原始输入的子部分：

Similarly, this code to search a BST for a value would be structural recursion, because the recursive calls are to subparts of the original input:

TreeNode* Find(TreeNode* root, DataType value) {
    if (root == nullptr) return nullptr;
    if (value < root->value) return Find(root->left, value);
    else return Find(root->right, value);

结构递归一词来源于这些结构（列表，BST等）可以递归定义：

The term "structural recursion" comes from the fact that these structures (lists, BSTs, etc.) can be defined recursively:

• 列表要么为空，要么为单元格，后跟一个列表。


• 二叉树要么什么都不是，要么是带有两个二叉树的子节点。

进行结构递归时，撤消将这些结构相互构建的操作。例如， NumberOfNodes 函数撤消采用节点并将其添加到现有列表之前的构造。 Find 运算符撤消将节点粘贴到其他两棵树的操作。因此，很容易看出为什么这些函数必须终止-最终，您首先撤消了用来建立对象的所有操作，然后递归停止了。

When doing structural recursion, you are "undoing" the operation from which these structures are built out of one another. For example, the NumberOfNodes function "undoes" the construction of taking a node and prepending it to an existing list. The Find operator "undoes" the operation of gluing a node to two other trees. Therefore, it's easy to see why these functions have to terminate - eventually, you "undo" all of the operations that went in to building up the object in the first place, and the recursion stops.

另一方面，考虑使用Quicksort，它会执行以下操作：

On the other hand, consider Quicksort, which does the following:

1. 选择一个轴心。


2. 创建三个新列表：小于枢轴的所有元素之一，大于枢轴的所有元素之一，和等于枢轴的所有元素之一。


3. 递归地排列这些列表的第一和第二个。


4. 连接较小，相等和较大值的列表。

1. Pick a pivot.
2. Create three new lists: one of all elements less than the pivot, one of all elements greater than the pivot, and one of all elements equal to the pivot.
3. Recursively sort the first and second of these lists.
4. Concatenate the list of smaller, equal, and larger values.

这里，递归调用是在较小数组上进行的，这些数组不是原始输入的一部分-列表必须从数据中创建。 （通常，实现会为这些列表重用空间，但不能保证这些子列表直接存在于输入中。）

Here, the recursive calls are being made on smaller arrays that weren't part of the original input - the lists had to be created from the data. (Typically, an implementation would reuse space for these lists, but those sublists weren't guaranteed to exist directly within the input).

自然数。通常，自然数的递归定义如下：

This distinction is blurry when it comes to natural numbers. Usually, natural numbers are recursively defined as follows:

• 0是自然数。


• 如果n是自然数，n + 1是自然数。


• 其他什么都不是自然数。

在此定义下，数字n是n + 1的部分。因此，此递归代码可计算n！是结构性递归：

Under this definition, the number n is a "part" of n + 1. Therefore, this recursive code to compute n! is structural recursion:

int Factorial(int n) {
    if (n == 0) return 1;
    return n * Factorial(n - 1);
}

这是结构性递归，因为参数n-1是部分

This is structural recursion, because the argument n - 1 was a "part" of the original input n.

类似地，根据此定义，计算第n个斐波那契数递归也算为结构性递归：

Similarly, by this definition, computing the nth Fibonacci number recursively counts as structural recursion:

int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

这被认为是结构性递归，因为n-1是n的一部分（形成通过撤消 +1），n-2是n-1的一部分（再次由撤消 +1形成）。

This is considered structural recursion because n - 1 is a part of n (formed by "undoing" the +1) and n - 2 is a part of n - 1 (again formed by "undoing" the +1).

，则此用于计算gcd的代码将被视为生成递归，而不是结构性递归：

On the other hand, this code to compute gcd would be considered generative recursion, rather than structural recursion:

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

原因是因为 a％b 是从 a 和 b 中计算的，而不是通过撤消一些

The reasoning is that since a % b is "computed" from a and b, rather than formed by "undoing" some number of +1 operations, the data is generated.

生成递归与结构递归之所以不同，是因为不能保证它会终止。例如，考虑以下函数：

The reason that generative recursion is different from structural recursion is that there's no guarantee that it terminates. For example, think about this function:

int BadTimes(int a, int b) {
    if (a == 0 && b == 0) return 0;
    return BadTimes(a * 2, b - 1);
}

此生成的递归函数永远不会终止： a 会变大，即使 b 会变小。

This generative recursive function never terminates: a keeps getting bigger even though b keeps getting smaller.

老实说，我从未听说过之前，我教过离散数学和程序设计课程。除非有人要求您知道其中的区别，否则我不会担心太多。

Honestly, I've never heard of this distinction before and I teach courses in discrete math and programming. I wouldn't worry too much about it unless someone is requiring you to know the difference.

希望这会有所帮助！

这篇关于结构递归与生成递归有何不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！