3

递归集和递归函数有什么区别？

4

3 回答 3

9

递归函数和递归集是可计算性理论中使用的术语。维基百科将它们定义如下：

一组自然数被称为可计算集（也称为可判定、递归或图灵可计算集），如果有一个图灵机，给定一个数 n，如果 n 在集合中，则停止并输出 1 并停止如果 n 不在集合中，则输出 0。如果有一个图灵机在输入 n 上停止并返回输出 f(n)，则从自然数到自身的函数 f 是递归或（图灵）可计算函数。

在这种情况下，递归函数并不意味着在编程语言中调用自身的函数。任何满足上述定义要求的数学函数都是递归函数，包括诸如恒等函数或将所有数字映射为1的函数（即无论输入如何都返回数字1）等微不足道的函数。

于 2009-12-05T21:47:52.230 回答
6

这些术语的含义因您的上下文而异。如果我们纯粹从编写程序的角度来讨论它们，那么递归集就没有多大意义。但是，可能只是我遇到过。也就是说，递归函数是在执行过程中调用自身的函数。斐波 那契数的计算是常见的经典示例：

/// <summary>A C# implementation of a function to return the nth Fibonacci number.</summary>
private static int Fibonacci(int n) {
 if (n <= 2) {
  return 1;
 } else {
  return Fibonacci(n - 1) + Fibonacci(n - 2);
 }
}

也就是说，在计算机科学，特别是计算理论的背景下，这些术语的另一个背景是在讨论形式语言时。在这种情况下，递归集被定义为存在可解成员问题的集合。例如，我们知道所有自然数的集合ℕ是一个递归集合，因为我们可以定义一个递归函数如下：

让f定义为一个函数，其中 f(x) = 1如果x ∈ ℕ并且 f(x) = 0如果x ∉ ℕ

递归集的概念对于可计算性的概念很重要，因为它导致递归可枚举集是一种可以被图灵机识别的语言（即图灵可识别）。对于这些语言，图灵机可能无法确定给定字符串是否是语言的成员，或者换句话说，机器可以接受、拒绝或循环。这与图灵可判定语言形成对比，对于该语言，机器将进入给定输入字符串的接受或拒绝状态。

这就是递归函数的概念发挥作用的地方，因为递归函数（或总递归函数）可以由图灵机计算并在每个输入时停止。其中，部分递归函数只能为图灵机计算，而不能保证停止行为。或者本质上，递归函数是递归集的对应物。

因此，为了让事情回到您最初的问题，在计算理论的背景下，递归集是可以生成（即枚举）或通过图灵机上的递归函数测试成员资格的东西。

延伸阅读：

于 2009-12-06T05:51:29.807 回答
5

也许问题应该是“为什么用‘递归’这个词来描述集合和函数？”

正如 Greg Hewgill 在他的评论中指出的那样，“绿色”这个词可以应用于苹果和汽车，但这并不意味着苹果和汽车之间存在关系。

我认为 Wikipedia 的引用使用术语“递归”作为“可计算”的同义词——作为程序员，我们会谨慎地同意这一点，但仅限于某些情况下。

于 2009-12-05T21:25:12.637 回答