27

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

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

4

1 回答 1

54

结构递归和生成递归之间的主要区别在于递归过程在哪里获取它所处理的数据以及它如何处理这些数据。具体来说，对于结构递归，对原始输入数据的子集进行递归调用。而对于生成递归，递归调用是对从原始输入数据构造/计算的数据进行的。

例如，如果要计算链表中元素的数量，可以执行以下操作：

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节点粘合到其他两棵树的操作。因此，很容易看出为什么这些函数必须终止 - 最终，您“撤消”了最初构建对象的所有操作，递归停止。

另一方面，考虑快速排序，它执行以下操作：

  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);
}

原因是，由于是从anda % b中“计算”出来的，而不是通过“撤消”一些 +1 操作而形成的，因此生成了数据。ab

生成递归与结构递归不同的原因是不能保证它会终止。例如，考虑这个函数：

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

这个生成递归函数永远不会终止：a即使b不断变小，也会不断变大。

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

希望这可以帮助！

于 2013-01-10T23:05:12.270 回答