结构递归与生成递归有何不同？

结构递归与生成递归有何不同？

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

例如，如果要计算链接列表中的元素数，则可以执行以下 *** 作：

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

这里，递归调用

NumberOfNodes

正在取得的

node->next

，这是一块它已经存在的原始投入。在这种情况下，递归通过将输入分解为较小的部分，然后在较小的部分上进行递归来进行。

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

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等）：

• 列表要么为空，要么为单元格，后跟一个列表。
• 二叉树要么什么都不是，要么是带有两个二叉树作为子节点的节点。

在进行结构递归时，您正在“撤消”从中相互构建这些结构的 *** 作。例如，

NumberOfNodes

函数“撤消”采用节点并将其添加到现有列表之前的构造。该

Find

运营商“撤销”胶合节点到其他两棵树的 *** 作。因此，很容易看出为什么这些函数必须终止-
最终，您首先“撤消”了最初用来构建对象的所有 *** 作，然后递归停止了。

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

1. 选择一个枢轴。
2. 创建三个新列表：小于枢轴的所有元素之一，大于枢轴的所有元素之一，和等于枢轴的所有元素之一。
3. 递归排序这些列表的第一和第二。
4. 连接较小，相等和较大值的列表。

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

对于自然数，这种区分是模糊的。通常，自然数递归定义如下：

• 0是自然数。
• 如果n是自然数，则n +1是自然数。
• 没有别的是自然数。

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

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

这是结构性递归，因为参数n-1是原始输入n的“一部分”。

同样，根据此定义，计算第n个斐波那契数递归计为结构递归：

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形成）。

另一方面，此计算gcd的代码将被视为生成性递归，而不是结构性递归：

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

原因是，由于

a % b

是从

a

和“计算”的

b

，而不是通过“撤消”一些+1 *** 作形成的，因此会生成数据。

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

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

这种生成的递归函数永远不会终止：

a

即使

b

不断变小，它也会不断变大。

老实说，我以前从未听说过这种区别，并且我教授离散数学和编程课程。除非有人要求您知道区别，否则我不会对此太担心。

希望这可以帮助！