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

Question

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

有人可以解释计算第n个斐波纳契数的函数和从1到N计算因子的函数是结构还是生成？

Answer 1

结构递归和生成递归之间的关键区别在于递归过程获取它所处理的数据以及它如何处理该数据.具体地,对于结构递归,对原始输入数据的子集进行递归调用.而对于生成递归,对从原始输入数据构造/计算的数据进行递归调用.

例如,如果要计算链接列表中的元素数,可以执行以下操作:

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个Fibonacci数递归计为结构递归:

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不断变小,它也会越来越大.

老实说,我以前从未听说过这种区别,我教过离散数学和编程课程.除非有人要求你知道差异,否则我不会太担心它.

希望这可以帮助!