结构递归和生成递归有什么区别？

Question

结构递归和生成递归有什么区别？

algorithmdata-structuresrecursion

32

我已经理解了维基百科中、关于生成递归的描述，但是对于结构递归的概念感到困惑。

请问有人能够解释一下计算第n个斐波那契数和计算1到N阶乘的函数是属于结构递归还是生成递归吗？

- A. K.

我的个人看法：根据该定义，斐波那契数列是生成递归的，因为数据在生成过程中就被“生成”了。而结构递归则是关于遍历[已有]图形的。文章继续指出一个重要的区别是，通过结构归纳，可以证明结构递归会终止。 - user166390

@pst- 我认为斐波那契实际上是结构递归。它并不是那么关于“生成”数据，而更关于如何想出递归调用的参数。 - templatetypedef

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

结构递归和生成递归的关键区别在于递归过程获取数据的方式以及如何处理数据。具体而言，对于结构递归，递归调用是在原始输入数据的子集上进行的。而对于生成递归，递归调用是在从原始输入数据构造/计算出的数据上进行的。

例如，如果你想要计算链表中元素的数量，可以采取以下方法：

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

在这里，对 node->next 进行了递归调用，它是原始输入中已经存在的一部分。在这种情况下，递归通过将输入拆分为较小的部分，然后对较小的部分进行递归来工作。

类似地，这个搜索二叉搜索树中的值的代码也是结构递归，因为递归调用是针对原始输入的子部分进行的：

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

推理是由于a % b是从a和b计算出来的，而不是通过“撤销”一些+1操作形成的，因此数据是生成的。

生成递归与结构递归不同的原因在于没有保证其终止。例如，请考虑以下函数：

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

这个生成递归函数永远不会终止：尽管b变得越来越小，但a仍然变得越来越大。

说实话，我以前从未听说过这种区别，而我教离散数学和编程课程。除非有人要求你知道这个区别，否则不必太担心。

希望这可以帮到你！