121

邮件列表和在线讨论中似乎经常出现的主题之一是攻读计算机科学学位的优点（或缺乏）。对于消极一方来说，似乎一次又一次出现的一个论点是，他们已经编码了几年，而且他们从未使用过递归。

所以问题是：

  1. 什么是递归？
  2. 我什么时候使用递归？
  3. 为什么人们不使用递归？
4

40 回答 40

86

在这个线程中有许多很好的递归解释，这个答案是关于为什么你不应该在大多数语言中使用它。*在大多数主要的命令式语言实现中（即 C、C++、Basic、Python 的每个主要实现、Ruby、Java 和 C#)迭代比递归更可取。

要了解原因，请浏览上述语言用于调用函数的步骤：

  1. 在堆栈上为函数的参数和局部变量开辟空间
  2. 函数的参数被复制到这个新空间
  3. 控制跳转到函数
  4. 函数的代码运行
  5. 函数的结果被复制到返回值中
  6. 堆栈回绕到其先前的位置
  7. 控制跳回到调用函数的地方

完成所有这些步骤需要时间，通常比遍历循环所花费的时间多一点。然而，真正的问题在于步骤#1。当许多程序启动时，它们为其堆栈分配一块内存，当它们用完该内存时（通常，但不总是由于递归），程序由于堆栈溢出而崩溃。

因此，在这些语言中，递归速度较慢，并且使您容易崩溃。尽管如此，仍然有一些使用它的论据。通常，一旦您知道如何阅读，递归编写的代码会更短且更优雅。

语言实现者可以使用一种称为尾调用优化的技术，它可以消除某些类别的堆栈溢出。简而言之：如果一个函数的返回表达式只是一个函数调用的结果，那么你不需要在堆栈上添加一个新的级别，你可以将当前的级别重用于被调用的函数。遗憾的是，很少有命令式语言实现内置了尾调用优化。

*我喜欢递归。 我最喜欢的静态语言根本不使用循环，递归是重复做某事的唯一方法。我只是不认为递归在没有针对它进行调整的语言中通常不是一个好主意。

** 顺便说一句，Mario，您的 ArrangeString 函数的典型名称是“join”，如果您选择的语言还没有实现它，我会感到惊讶。

于 2008-08-06T05:09:44.770 回答
63

递归的简单英文示例。

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.
于 2010-05-04T16:38:20.530 回答
49

在最基本的计算机科学意义上，递归是一个调用自身的函数。假设您有一个链表结构：

struct Node {
    Node* next;
};

你想知道一个链表有多长，你可以用递归来做到这一点：

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

（这当然也可以通过 for 循环来完成，但作为概念的说明很有用）

于 2010-05-04T11:25:33.620 回答
46

每当一个函数调用自己，创建一个循环，那就是递归。与任何事情一样，递归也有好的用途和坏的用途。

最简单的例子是尾递归，函数的最后一行是对自身的调用：

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

然而，这是一个蹩脚的、几乎毫无意义的例子，因为它很容易被更有效的迭代所取代。毕竟，递归受到函数调用开销的影响，在上面的示例中，与函数本身的操作相比，这可能是相当大的。

因此，进行递归而不是迭代的全部原因应该是利用调用堆栈来做一些聪明的事情。例如，如果您在同一个循环中多次使用不同的参数调用一个函数，那么这是一种完成分支的方法。一个典型的例子是谢尔宾斯基三角形。

在此处输入图像描述

您可以使用递归非常简单地绘制其中一个，其中调用堆栈在 3 个方向上分支：

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

如果你尝试用迭代做同样的事情，我想你会发现它需要更多的代码来完成。

其他常见用例可能包括遍历层次结构，例如网站爬虫、目录比较等。

结论

实际上，只要您需要迭代分支，递归就最有意义。

于 2010-05-04T13:33:03.223 回答
27

递归是一种基于分而治之思维的解决问题的方法。基本思想是你把原始问题分成更小的（更容易解决的）实例，解决那些更小的实例（通常再次使用相同的算法），然后将它们重新组合成最终的解决方案。

典型示例是生成 n 的阶乘的例程。n 的阶乘是通过将 1 和 n 之间的所有数字相乘来计算的。C# 中的迭代解决方案如下所示：

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

迭代解决方案并不令人惊讶，任何熟悉 C# 的人都应该理解它。

通过识别第 n 个阶乘是 n * Fact(n-1) 来找到递归解决方案。或者换一种说法，如果你知道一个特定的阶乘数是什么，你就可以计算下一个阶乘数。这是 C# 中的递归解决方案：

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

该函数的第一部分称为基本案例（或有时称为保护子句），是防止算法永远运行的原因。每当使用 1 或更小的值调用函数时，它只会返回值 1。第二部分更有趣，被称为递归步骤。在这里，我们使用稍微修改的参数调用相同的方法（我们将其减 1），然后将结果与我们的 n 副本相乘。

当第一次遇到这可能会有点令人困惑，因此检查它在运行时的工作原理是有启发性的。假设我们调用 FactRec(5)。我们进入了例程，没有被基本情况所接受，所以我们最终是这样的：

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

如果我们使用参数 4 重新输入方法，我们再次不会被保护子句停止，因此我们最终会出现：

// In FactRec(4)
return 4 * FactRec(3);

如果我们将此返回值替换为上面的返回值，我们得到

// In FactRec(5)
return 5 * (4 * FactRec(3));

这应该为您提供有关如何得出最终解决方案的线索，因此我们将快速跟踪并展示下降过程中的每一步：

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

当基本情况被触发时，就会发生最终的替换。在这一点上，我们有一个简单的代数公式来求解，它首先直接等同于阶乘的定义。

请注意，对方法的每次调用都会导致触发基本情况或调用参数更接近基本情况的同一方法（通常称为递归调用）。如果不是这种情况，那么该方法将永远运行。

于 2008-08-06T02:54:58.850 回答
12

递归是通过调用自身的函数来解决问题。一个很好的例子是阶乘函数。阶乘是一个数学问题，其中 5 的阶乘是 5 * 4 * 3 * 2 * 1。这个函数在 C# 中解决了正整数的这个问题（未经测试 - 可能存在错误）。

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}
于 2010-05-04T11:29:21.350 回答
9

考虑一个古老的、众所周知的问题：

在数学中，两个或多个非零整数的最大公约数(gcd) ... 是除以数字而没有余数的最大正整数。

gcd 的定义非常简单：

gcd 定义

其中 mod 是模运算符（即整数除法后的余数）。

在英语中，这个定义说任何数字和零的最大公约数是那个数字，两个数字m和n的最大公约数是n的最大公约数以及m除以n后的余数。

如果您想知道为什么会这样，请参阅有关欧几里得算法的 Wikipedia 文章。

让我们以 gcd(10, 8) 为例。每一步都等于它之前的一步：

  1. gcd(10, 8)
  2. gcd(10, 10 mod 8)
  3. gcd(8, 2)
  4. gcd(8, 8 模 2)
  5. gcd(2, 0)
  6. 2

在第一步中，8 不等于 0，因此适用定义的第二部分。10 mod 8 = 2 因为 8 进入 10 一次，余数为 2。在步骤 3，第二部分再次应用，但这次 8 mod 2 = 0 因为 2 除以 8，没有余数。在第 5 步，第二个参数是 0，所以答案是 2。

您是否注意到 gcd 出现在等号的左侧和右侧？数学家会说这个定义是递归的，因为您定义的表达式在其定义中重复出现。

递归定义往往是优雅的。例如，列表和的递归定义是

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

wherehead是列表中的第一个元素，是列表tail的其余部分。请注意，sum它最后在其定义中重复出现。

也许您更喜欢列表中的最大值：

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

您可以递归地定义非负整数的乘法以将其转换为一系列加法：

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

如果关于将乘法转换为一系列加法的那一点没有意义，请尝试扩展一些简单的示例以了解它是如何工作的。

合并排序有一个可爱的递归定义：

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

如果您知道要查找什么，那么递归定义无处不在。请注意所有这些定义如何具有非常简单的基本情况，例如gcd(m, 0) = m。递归案例减少了问题，以得到简单的答案。

有了这个理解，你现在可以欣赏维基百科关于递归的文章中的其他算法了！

于 2010-05-04T13:58:17.817 回答
9

递归是指通过解决问题的较小版本然后使用该结果加上一些其他计算来制定原始问题的答案来解决问题的方法。很多时候，在解决较小版本的过程中，该方法会解决问题的较小版本，依此类推，直到达到一个难以解决的“基本情况”。

例如，要计算数字 的阶乘X，可以将其表示为X times the factorial of X-1。因此，该方法“递归”以找到 的阶乘X-1，然后乘以它得到的任何结果X以给出最终答案。当然，要找到 的阶乘X-1，首先要计算 的阶乘X-2，以此类推。基本情况是何时为 0 或 1，在这种情况下，它知道从X开始返回。10! = 1! = 1

于 2010-05-04T11:26:02.030 回答
8
  1. 调用自身的函数
  2. 当一个函数可以（很容易）分解成一个简单的操作加上在问题的某个较小部分上的相同函数时。相反，我应该说，这使它成为递归的一个很好的候选者。
  3. 他们是这样！

典型的例子是阶乘，它看起来像：

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

一般来说，递归不一定很快（函数调用开销往往很高，因为递归函数往往很小，见上文）并且可能会遇到一些问题（堆栈溢出任何人？）。有人说他们往往很难在非平凡的情况下得到“正确”，但我并不真正相信这一点。在某些情况下，递归最有意义，并且是编写特定函数的最优雅和最清晰的方式。应该注意的是，某些语言更喜欢递归解决方案并对其进行更多优化（想到 LISP）。

于 2008-08-06T02:35:07.437 回答
6

递归函数是调用自身的函数。我发现使用它的最常见原因是遍历树结构。例如，如果我有一个带有复选框的 TreeView（考虑安装一个新程序，“选择要安装的功能”页面），我可能想要一个“检查所有”按钮，它会是这样的（伪代码）：

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

所以你可以看到 checkRecursively 首先检查它传递的节点，然后为该节点的每个子节点调用自身。

你确实需要小心递归。如果你进入一个无限递归循环，你会得到一个 Stack Overflow 异常 :)

我想不出人们在适当的时候不应该使用它的理由。它在某些情况下很有用，而在其他情况下则不然。

我认为因为它是一种有趣的技术，一些编码人员最终可能会比他们应该更频繁地使用它，而没有真正的理由。这在某些圈子中给递归起了一个坏名声。

于 2008-08-06T02:44:53.317 回答
5

递归是直接或间接引用自身的表达式。

考虑递归首字母缩写词作为一个简单的例子：

  • GNU代表GNU's Not Unix
  • PHP代表PHP：超文本预处理器
  • YAML代表YAML 不是标记语言
  • WINE代表Wine Is Not an Emulator
  • VISA代表签证国际服务协会

维基百科上的更多示例

于 2010-05-04T11:56:43.173 回答
4

递归最适用于我喜欢称之为“分形问题”的问题，在这种情况下，您正在处理由该大事物的较小版本组成的大事物，每个大事物都是该事物的更小版本，依此类推。如果您必须遍历或搜索诸如树或嵌套的相同结构之类的东西，那么您遇到的问题可能是递归的一个很好的候选者。

人们避免递归的原因有很多：

  1. 与函数式编程相反，大多数人（包括我自己）都在过程或面向对象编程方面切身。对于这些人来说，迭代方法（通常使用循环）感觉更自然。

  2. 我们这些在过程或面向对象编程方面磨练编程的人经常被告知要避免递归，因为它容易出错。

  3. 我们经常被告知递归很慢。重复调用和从例程返回涉及大量的堆栈推送和弹出，这比循环慢。我认为有些语言比其他语言处理得更好，而且这些语言很可能不是那些主要范式是过程或面向对象的语言。

  4. 对于我使用过的至少几种编程语言，我记得听到过一些建议，如果递归超过了一定深度，就不要使用它，因为它的堆栈不是那么深。

于 2008-08-06T03:12:15.507 回答
4

这是一个简单的例子：一个集合中有多少个元素。（有更好的方法来计算事物，但这是一个很好的简单递归示例。）

首先，我们需要两条规则：

  1. 如果集合为空，则集合中的项目数为零（呃！）。
  2. 如果集合不为空，则计数为一加上删除一项后集合中的项目数。

假设你有一个这样的集合：[xxx]。让我们数一数有多少项目。

  1. 集合是非空的[xxx]，所以我们应用规则2。项目数是[xx] 中的项目数加1（即我们删除了一个项目）。
  2. 集合是 [xx]，所以我们再次应用规则 2：1 + [x] 中的项目数。
  3. 集合是 [x]，它仍然匹配规则 2：1 + [] 中的项目数。
  4. 现在集合是 []，它符合规则 1：计数为零！
  5. 现在我们知道步骤 4 (0) 的答案，我们可以解决步骤 3 (1 + 0)
  6. 同样，现在我们知道步骤 3 (1) 中的答案，我们可以解决步骤 2 (1 + 1)
  7. 最后，现在我们知道步骤 2 (2) 中的答案，我们可以解决步骤 1 (1 + 2) 并获得 [xxx] 中的项目数，即 3。万岁！

我们可以将其表示为：

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

应用递归解决方案时，通常至少有 2 条规则：

  • 基础，一个简单的案例，它说明了当您“用完”所有数据时会发生什么。这通常是“如果您没有要处理的数据，您的答案是 X”的一些变体
  • 递归规则，它说明如果您仍然有数据会发生什么。这通常是某种规则，它说“做一些事情来缩小你的数据集，并将你的规则重新应用到更小的数据集”。

如果我们将上面的内容翻译成伪代码，我们会得到：

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

还有更多有用的示例（例如，遍历一棵树），我相信其他人会介绍这些示例。

于 2008-08-06T03:12:38.190 回答
4

递归语句是您将下一步要做什么的过程定义为输入和您已经完成的组合的语句。

例如，采用阶乘：

factorial(6) = 6*5*4*3*2*1

但很容易看出 factorial(6) 也是：

6 * factorial(5) = 6*(5*4*3*2*1).

所以一般来说：

factorial(n) = n*factorial(n-1)

当然，递归的棘手之处在于，如果您想根据已经完成的内容来定义事物，则需要从某个地方开始。

在这个例子中，我们只是通过定义 factorial(1) = 1 来做一个特例。

现在我们从下往上看：

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

由于我们定义了 factorial(1) = 1，我们到达了“底部”。

一般来说，递归过程有两个部分：

1）递归部分，它根据新输入定义一些过程，并结合您通过相同过程“已经完成”的内容。（即factorial(n) = n*factorial(n-1)）

2）一个基础部分，通过给它一些开始的地方来确保该过程不会永远重复（即factorial(1) = 1）

一开始你的头脑可能会有点混乱，但只要看看一堆例子，它们就应该融合在一起。如果您想更深入地理解这个概念，请学习数学归纳法。另外，请注意，某些语言针对递归调用进行了优化，而其他语言则没有。如果您不小心，很容易制作出异常缓慢的递归函数，但是在大多数情况下，也有一些技巧可以使它们具有高性能。

希望这可以帮助...

于 2010-05-04T13:30:28.267 回答
4

我喜欢这个定义：
在递归中，例程自己解决问题的一小部分，将问题分成更小的部分，然后调用自身来解决每个更小的部分。

我也喜欢 Steve McConnells 在 Code Complete 中对递归的讨论，他批评了计算机科学书籍中关于递归的示例。

不要对阶乘或斐波那契数使用递归

计算机科学教科书的一个问题是它们提供了愚蠢的递归示例。典型的例子是计算阶乘或计算斐波那契数列。递归是一个强大的工具，在这两种情况下使用它真的很愚蠢。如果为我工作的程序员使用递归来计算阶乘，我会雇用其他人。

我认为这是一个非常有趣的观点，并且可能是递归经常被误解的原因。

编辑：这不是对 Dav 的回答的挖掘——当我发布这个时我没有看到那个回复

于 2010-05-04T11:29:17.373 回答
4

1.) 一个方法是递归的，如果它可以调用自己；直接：

void f() {
   ... f() ... 
}

或间接地：

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) 何时使用递归

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) 人们只有在编写迭代代码非常复杂时才使用递归。例如，像前序、后序这样的树遍历技术可以迭代和递归。但通常我们使用递归，因为它很简单。

于 2014-03-11T09:47:20.470 回答
3

一个例子：一个楼梯的递归定义是：一个楼梯包括： - 一个台阶和一个楼梯（递归） - 或只有一个台阶（终止）

于 2010-05-04T13:34:56.237 回答
3

嗯，这是一个相当不错的定义。维基百科也有很好的定义。所以我会为你添加另一个（可能更糟的）定义。

当人们提到“递归”时，他们通常是在谈论他们编写的一个函数，该函数反复调用自身，直到完成它的工作。遍历数据结构中的层次结构时，递归会很有帮助。

于 2010-05-04T11:27:09.717 回答
2

递归函数是一个包含对自身的调用的函数。递归结构是包含自身实例的结构。您可以将两者组合为一个递归类。递归项的关键部分是它包含自身的实例/调用。

考虑两个彼此面对的镜子。我们已经看到了它们所产生的简洁的无限效应。每个反射都是镜子的一个实例，它包含在镜子的另一个实例中，等等。包含自身反射的镜子是递归的。

二叉搜索树是递归的一个很好的编程示例。该结构是递归的，每个节点包含一个节点的 2 个实例。在二叉搜索树上工作的函数也是递归的。

于 2010-05-04T16:46:56.280 回答
2

对已解决的问题进行递归：什么都不做，你就完成了。
递归一个未解决的问题：执行下一步，然后递归其余的。

于 2008-08-06T03:32:35.730 回答
2

这是一个老问题，但我想从逻辑的角度添加一个答案（即不是从算法正确性的角度或性能的角度）。

我使用 Java 工作，Java 不支持嵌套函数。因此，如果我想做递归，我可能必须定义一个外部函数（它的存在只是因为我的代码违反了 Java 的官僚规则），或者我可能不得不完全重构代码（我真的很讨厌这样做）。

因此，我经常避免递归，而是使用堆栈操作，因为递归本身本质上是一个堆栈操作。

于 2014-08-30T10:09:20.510 回答
2

用简单的英语：假设你可以做 3 件事：

  1. 拿一个苹果
  2. 写下计数标记
  3. 计数计数标记

你面前的桌子上有很多苹果，你想知道有多少苹果。

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

重复同一件事直到完成的过程称为递归。

我希望这是您正在寻找的“简单的英语”答案！

于 2010-05-04T13:09:33.857 回答
1

函数调用自己或使用自己的定义。

于 2010-05-04T13:59:55.677 回答
1

你想在任何时候使用它，只要你有一个树形结构。它在读取 XML 时非常有用。

于 2008-08-21T13:18:19.180 回答
1

递归是指您有一个使用自身的操作。它可能会有一个停止点，否则它将永远持续下去。

假设您想在字典中查找一个单词。您可以使用称为“查找”的操作。

你的朋友说“我现在真的可以舀一些布丁！” 你不知道他是什么意思，所以你在字典里查了“勺子”，它的内容是这样的：

勺子：名词——末端有圆勺的器具。勺子：动词 - 在某物上使用勺子 勺子：动词 - 从背后紧紧拥抱

现在，由于您的英语真的不好，这为您指明了正确的方向，但您需要更多信息。所以你选择“器物”和“拥抱”来查找更多信息。

拥抱：动词-依偎器具：名词-工具，通常是餐具

嘿！你知道什么是依偎，它与布丁无关。你也知道布丁是你吃的东西，所以现在说得通了。你的朋友一定想用勺子吃布丁。

好的，好的，这是一个非常蹩脚的例子，但它说明了（可能很糟糕）递归的两个主要部分。1）它使用自己。在这个例子中，在你理解一个词之前，你并没有真正有意义地查找一个词，这可能意味着要查找更多的词。这将我们带到第二点，2）它停在某个地方。它必须有某种基本情况。否则，您最终只会查找字典中的每个单词，这可能不太有用。我们的基本情况是，您获得了足够的信息，以便在您之前做过和不了解的事情之间建立联系。

给出的传统示例是阶乘，其中 5 阶乘是 1*2*3*4*5（即 120）。基本情况为 0（或 1，取决于）。因此，对于任何整数 n，您执行以下操作

n 等于 0 吗？否则返回 1，返回 n *（n-1 的阶乘）

让我们以 4 为例（我们提前知道是 1*2*3*4 = 24）。

4的阶乘……是0吗？不，所以它必须是 3 的 4 * 阶乘，但 3 的阶乘是什么？它是 3 * 2 的阶乘 2 的阶乘是 2 * 1 的阶乘 1 的阶乘是 1 * 0 的阶乘，我们知道 0 的阶乘！:-D 它是 1，即定义 1 的阶乘是 1 * 0 的阶乘，即 1... 所以 1*1 = 2 的 1 阶乘是 2 * 1 的阶乘，即 1... 所以 2* 1 = 3 的 2 阶乘是 3 * 2 的阶乘，即 2... 所以 3*2 = 4 的 6 阶乘（终于！！）是 4 * 3 的阶乘，即 6... 4*6 是24

阶乘是“基本案例，并使用自身”的简单案例。

现在，请注意，我们一直在处理 4 的阶乘……如果我们想要 100 的阶乘，我们必须一直降到 0……这可能会有很多开销。以同样的方式，如果我们在字典中查找一个晦涩的单词，可能需要查找其他单词并扫描上下文线索，直到找到我们熟悉的连接。递归方法可能需要很长时间才能完成。但是，如果正确使用并理解它们，它们可以使复杂的工作变得异常简单。

于 2010-05-04T16:04:40.107 回答
1

递归的最简单定义是“自引用”。引用自身（即调用自身）的函数是递归的。要记住的最重要的事情是，递归函数必须具有“基本情况”，即如果为真则使其不调用自身并因此终止递归的条件。否则你将有无限递归：

递归 http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

于 2010-05-04T16:10:15.793 回答
1

递归是方法调用自身以执行特定任务的过程。它减少了代码的冗余。大多数递归函数或方法必须有一个条件来中断递归调用，即在满足条件时阻止它调用自身——这可以防止创建无限循环。并非所有函数都适合递归使用。

于 2010-05-04T12:42:48.490 回答
1

计算中的递归是一种用于计算从单个函数（方法、过程或块）调用正常返回后的结果或副作用的技术。

根据定义，递归函数必须能够根据退出条件或未满足的条件直接或间接（通过其他函数）调用自身。如果满足退出条件，则特定调用将返回给它的调用者。这一直持续到从返回初始调用，此时所需的结果或副作用将可用。

例如，这是一个在 Scala 中执行 Quicksort 算法的函数（从 Scala 的 Wikipedia 条目复制）

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

在这种情况下，退出条件是一个空列表。

于 2010-05-04T14:14:42.047 回答
1

在简单的英语中，递归意味着一次又一次地重复某些事情。

在编程中，一个例子是调用自身内部的函数。

请看以下计算数字阶乘的示例：

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
于 2010-05-04T12:48:44.663 回答
1

嘿，对不起，如果我的意见同意某人，我只是想用简单的英语解释递归。

假设您有三位经理——杰克、约翰和摩根。Jack 管理 2 个程序员，John - 3 和 Morgan - 5。你将给每个经理 300 美元，并且想知道它会花多少钱。答案很明显——但如果摩根的 2 名员工也是经理呢？

递归来了。您从层次结构的顶部开始。夏季费用为 0 美元。你从杰克开始，然后检查他是否有任何经理作为员工。如果您发现其中任何一个，请检查他们是否有任何经理作为员工等等。每次找到经理时，夏季费用都会增加 300 美元。当你和杰克谈完后，去找约翰，他的员工，然后去找摩根。

你永远不会知道，在得到答案之前你会经历多少周期，尽管你知道你有多少经理以及你可以花费多少预算。

递归是一棵树，有枝有叶，分别称为父母和孩子。当您使用递归算法时，您或多或少有意识地从数据中构建一棵树。

于 2010-05-04T12:50:05.383 回答
1

应用于编程的递归基本上是从其自己的定义（自身内部）中调用一个函数，使用不同的参数来完成一项任务。

于 2010-05-04T11:25:53.683 回答
1

很多问题可以分为两种类型：

  1. 基本案例，这是您可以通过查看它们来解决的基本问题，以及
  2. 递归案例，从较小的部分（基本或其他）构建一个更大的问题。

那么什么是递归函数呢？好吧，这就是您拥有直接或间接根据自身定义的功能的地方。好吧，这听起来很荒谬，直到您意识到它对上述类型的问题是明智的：您直接解决基本情况并通过使用递归调用来处理递归情况，以解决嵌入其中的较小问题。

需要递归（或闻起来很像的东西）的真正经典示例是在处理一棵树时。树的叶子是基本情况，分支是递归情况。（在伪 C 中。）

struct Tree {
    int leaf;
    Tree *leftBranch;
    Tree *rightBranch;
};

打印出来的最简单的方法是使用递归：

function printTreeInOrder(Tree *tree) {
    if (tree->leftBranch) {
        printTreeInOrder(tree->leftBranch);
    }
    print(tree->leaf);
    if (tree->rightBranch) {
        printTreeInOrder(tree->rightBranch);
    }
}

很容易看出这会奏效，因为它非常清晰。（非递归等价物要复杂得多，需要一个内部堆栈结构来管理要处理的事物列表。）当然，假设没有人完成循环连接。

在数学上，证明递归被驯服的诀窍是专注于找到参数大小的度量。对于我们的树示例，最简单的度量是当前节点下方树的最大深度。在叶子上，它是零。在一个只有叶子下面的分支上，它是一个，等等。然后你可以简单地表明，为了处理树，调用函数的参数的大小有严格的顺序；在度量的意义上，递归调用的参数总是比整体调用的参数“小”。使用严格递减的基数指标，您已排序。

无限递归也是可能的。这很混乱，而且在许多语言中都无法工作，因为堆栈爆炸了。（在它起作用的地方，语言引擎必须确定该函数以某种方式不会返回，因此能够优化堆栈的保留。一般来说是棘手的东西；尾递归只是最简单的方法.)

于 2010-05-04T15:29:26.027 回答
1

如果基本上由一个 switch 语句组成，并且每个数据类型的 case 都有一个 case，那么任何算法都表现出对数据类型的结构递归。

例如，当你在处理一个类型时

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

结构递归算法将具有以下形式

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

这确实是编写适用于数据结构的任何算法的最明显方法。

现在，当您查看使用 Peano 公理定义的整数（嗯，自然数）时

 integer = 0 | succ(integer)

你看到整数的结构递归算法看起来像这样

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

众所周知的阶乘函数是这种形式最简单的例子。

于 2010-05-04T13:53:14.483 回答
1

“如果我有一把锤子，让一切看起来都像钉子。”

递归是解决大问题的一种策略，每一步都只是“把两件小事变成一件大事”，每次都用同一个锤子。

例子

假设你的办公桌上堆满了 1024 份杂乱无章的文件。你如何使用递归从乱七八糟的文件中制作出整齐、干净的一摞文件？

  1. 划分：将所有纸张展开，因此每个“堆栈”中只有一张。
  2. 征服：
    1. 四处走动，将每张纸放在另一张纸上。你现在有 2 个堆栈。
    2. 四处走动，将每个 2 堆放在另一个 2 堆的顶部。你现在有 4 个堆栈。
    3. 四处走动，将每个 4 堆放在另一个 4 堆的顶部。你现在有 8 个堆栈。
    4. ... 不断...
    5. 您现在有一大叠 1024 张纸！

请注意，这非常直观，除了计算所有内容（这不是绝对必要的）。实际上，您可能不会一直到 1 页堆栈，但您可以并且它仍然可以工作。重要的部分是锤子：用你的手臂，你总是可以将一个堆栈放在另一个之上以形成更大的堆栈，并且（在合理范围内）任何一个堆栈有多大都无关紧要。

于 2010-05-04T11:54:34.753 回答
1

递归是根据自身定义函数、集合或算法的技术。

例如

n! = n(n-1)(n-2)(n-3)...........*3*2*1

现在它可以递归定义为：-

n! = n(n-1)!   for n>=1

在编程术语中，当一个函数或方法重复调用自己，直到满足某个特定条件时，这个过程称为递归。但必须有终止条件，函数或方法不能进入无限循环。

于 2010-05-04T15:22:16.847 回答
1

它是一种无限期地反复做事的方法，以便使用每个选项。

例如，如果您想获取 html 页面上的所有链接，您将需要递归，因为当您获取第 1 页上的所有链接时，您将希望获取第一页上找到的每个链接上的所有链接。然后对于指向新页面的每个链接，您将需要这些链接等等......换句话说，它是一个从自身内部调用自身的函数。

当您这样做时，您需要一种方法来知道何时停止，否则您将处于无限循环中，因此您向函数添加一个整数参数以跟踪循环数。

在 c# 中你会得到这样的东西：

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}
于 2010-05-04T12:02:28.687 回答
0

实际上，阶乘的更好递归解决方案应该是：

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

因为这个版本是尾递归的

于 2008-08-21T13:39:47.037 回答
0

我创建了一个递归函数来连接字符串列表和它们之间的分隔符。我主要使用它来创建 SQL 表达式，通过将字段列表作为“项目”和“逗号+空格”作为分隔符传递。这是函数（它使用一些 Borland Builder 本地数据类型，但可以适应任何其他环境）：

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

我这样称呼它：

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

假设您有一个名为“ fields ”的数组，其中包含以下数据：“ albumName ”、 “ releaseDate ”、“ labelId ”。然后调用函数：

ArrangeString(fields, 0, ", ");

随着函数开始工作，变量' result '接收到数组位置0的值，即' albumName '。

然后它检查它正在处​​理的位置是否是最后一个。如果不是，那么它将结果与分隔符和函数的结果连接起来，哦，上帝，这就是同一个函数。但是这一次，检查一下，它称自己在位置上加 1。

ArrangeString(fields, 1, ", ");

它不断重复，创建一个 LIFO 堆，直到它到达正在处理的位置是最后一个位置的点，因此该函数仅返回列表中该位置上的项目，不再连接。然后将堆向后连接。

知道了？如果你不这样做，我有另一种方式来解释它。:o)

于 2008-08-06T03:00:16.547 回答
0

我使用递归。这与拥有计算机科学学位有什么关系......（顺便说一句，我没有）

我发现的常见用途：

  1. 站点地图- 从文档根目录开始通过文件系统递归
  2. 蜘蛛- 爬过网站以查找电子邮件地址、链接等。
  3. ?
于 2008-08-06T03:13:35.817 回答
0

马里奥，我不明白你为什么在那个例子中使用递归。为什么不简单地遍历每个条目？像这样的东西：

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

上述方法会更快，也更简单。无需使用递归来代替简单的循环。我认为这些例子就是为什么递归会受到不好的批评。即使是典型的阶乘函数示例也可以通过循环更好地实现。

于 2008-08-06T03:19:31.920 回答