什么是递归以及何时应该使用它？

Question

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

所以问题是：

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

Answer 1

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

要了解原因，请完成上述语言调用函数的步骤：

1. 空间被雕刻在 堆栈 对于函数的参数和局部变量
2. 函数的参数被复制到这个新空间中
3. 控制跳转到函数
4. 函数的代码运行
5. 函数的结果被复制到返回值中
6. 堆栈回退到之前的位置
7. 控制跳转回函数被调用的地方

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

因此，在这些语言中，递归速度较慢，并且很容易崩溃。但对于使用它仍然存在一些争论。一般来说，一旦您知道如何阅读，递归编写的代码会更短且更优雅。

语言实现者可以使用一种称为 尾调用优化 这可以消除某些类型的堆栈溢出。简单地说：如果函数的返回表达式只是函数调用的结果，那么您不需要在堆栈上添加新的级别，您可以为正在调用的函数重用当前的级别。遗憾的是，很少有命令式语言实现内置了尾部调用优化。

* 我喜欢递归。 我最喜欢的静态语言 根本不使用循环，递归是重复执行某些操作的唯一方法。我只是认为对于不适合递归的语言来说，递归通常不是一个好主意。

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

Answer 2

简单的英文递归例子。

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.

Answer 3

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

struct Node {
    Node* next;
};

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

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

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

Answer 4

每当一个函数调用自身并创建一个循环时，这就是递归。与任何事物一样，递归也有好的用途和坏的用途。

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

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

如果您尝试通过迭代做同样的事情，我想您会发现需要更多的代码才能完成。

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

结论

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

Answer 5

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

典型的例子是生成 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))));

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

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

Answer 6

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

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

    return n * Factorial(n - 1);
}

Answer 7

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

例如，计算数字的阶乘 X, ，可以将其表示为 X times the factorial of X-1. 。因此，该方法“递归”来查找 X-1, ，然后乘以得到的值 X 给出最终答案。当然，要求出阶乘 X-1, ，它首先计算阶乘 X-2, ， 等等。基本情况是 X 是 0 或 1，在这种情况下它知道返回 1 自从 0! = 1! = 1.

Answer 8

考虑一个 老的众所周知的问题:

在数学中， 最大公约数 (gcd) … 两个或多个非零整数的最大正整数，可将这些数字相除而无余数。

gcd 的定义出奇的简单：

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

在英语中，这个定义表示任何数字的最大公约数和零就是该数字，并且两个数字的最大公约数 米 和 n 是最大公约数 n 以及除法后的余数 米 经过 n.

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

我们以计算 gcd(10, 8) 为例。每一步都与之前的一步相同：

1. 最大公约数(10, 8)
2. gcd(10, 10 模 8)
3. 最大公约数(8, 2)
4. gcd(8, 8 模 2)
5. 最大公约数(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))

在哪里 head 是列表中的第一个元素并且 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。递归案例逐渐解决问题，得到简单的答案。

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

Answer 9

1. 一个调用自身的函数
2. 当一个函数可以（轻松）分解为一个简单的操作加上同一函数解决问题的较小部分时。相反，我应该说，这使其成为递归的良好候选者。
3. 他们是这样！

典型的例子是阶乘，如下所示：

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

  return a*fact(a-1);
}

一般来说，递归不一定很快（函数调用开销往往很高，因为递归函数往往很小，见上文），并且可能会遇到一些问题（堆栈溢出有人吗？）。有人说，在重要的情况下，它们往往很难做到“正确”，但我并不真正相信这一点。在某些情况下，递归是最有意义的，也是编写特定函数的最优雅、最清晰的方式。应该指出的是，某些语言支持递归解决方案并对其进行更多优化（例如 LISP）。

Answer 10

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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

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

您确实需要小心递归。如果你进入无限递归循环，你将得到一个堆栈溢出异常:)

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

我认为，因为这是一种有趣的技术，一些程序员最终可能会在没有真正理由的情况下更频繁地使用它。这在某些圈子里给递归带来了坏名声。

Answer 11

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

将递归首字母缩略词视为一个简单的示例：

• GNU 代表 GNU 不是 Unix
• PHP 代表 PHP：超文本预处理器
• YAML 代表 YAML 不是标记语言
• 葡萄酒 代表 Wine 不是模拟器
• 签证 代表 Visa国际服务协会

维基百科上的更多示例

Answer 12

递归最适合我所说的“分形问题”，在这种情况下，您正在处理一个由该大事物的较小版本组成的大事物，每个大事物都是该大事物的更小的版本，等等。如果您必须遍历或搜索树或嵌套的相同结构之类的东西，那么您遇到的问题可能很适合递归。

人们出于多种原因避免递归：

1. 大多数人（包括我自己）都是通过过程式或面向对象编程而不是函数式编程来学习编程的。对于这些人来说，迭代方法（通常使用循环）感觉更自然。

2. 我们这些刚刚接触过程式或面向对象编程的人经常被告知要避免递归，因为它很容易出错。

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

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

Answer 13

递归语句是一种将下一步操作的过程定义为输入和已完成操作的组合的语句。

例如，取阶乘：

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

但很容易看出阶乘（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

由于我们定义了阶乘(1) = 1，所以我们到达了“底部”。

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

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

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

一开始你可能会有点困惑，但只要看一堆例子，你就应该明白一切了。如果您想更深入地理解这个概念，请学习数学归纳法。另外，请注意，某些语言针对递归调用进行了优化，而另一些语言则没有。如果你不小心的话，很容易做出极其缓慢的递归函数，但也有一些技术可以使它们在大多数情况下保持高性能。

希望这可以帮助...

Answer 14

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

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

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

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

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

编辑：这并不是对 Dav 答案的挖苦 - 当我发布此内容时我没有看到该回复

Answer 15

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.) 人们仅在编写迭代代码非常复杂时才使用递归。例如，像前序、后序这样的树遍历技术可以是迭代的和递归的。但通常我们使用递归，因为它简单。

Answer 16

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

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

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

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

1. 集合是 [x x x]，它不为空，所以我们应用规则 2。项目数是 [x x] 中的项目数加一（即我们删除了一个项目）。
2. 集合是 [x x]，所以我们再次应用规则 2：一 + [x] 中的项目数。
3. 集合是 [x]，仍然符合规则 2：一 + [] 中的项目数。
4. 现在集合是 []，它符合规则 1：计数为零！
5. 现在我们知道了步骤 4 (0) 的答案，我们可以求解步骤 3 (1 + 0)
6. 同样，既然我们知道了步骤 3 (1) 的答案，我们就可以求解步骤 2 (1 + 1)
7. 最后，现在我们知道了步骤 2 (2) 中的答案，我们可以求解步骤 1 (1 + 2) 并获得 [x x x] 中的项目数，即 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)

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

Answer 17

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

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

Answer 18

一个例子：楼梯的递归定义是：楼梯由以下部分组成：- 一个步骤和一个楼梯（递归） - 或仅一个步骤（终止）

Answer 19

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

Answer 20

用简单的英语来说：假设你可以做三件事：

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

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

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

Answer 21

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

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

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

Answer 22

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

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

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

Answer 23

您希望在拥有树结构的任何时候都可以使用它。它在读取 XML 时非常有用。

Answer 24

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

Answer 25

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

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

例子

假设你的桌子上堆满了 1024 张杂乱无章的文件。如何使用递归从混乱中整理出一叠整齐、干净的文件？

1. 划分： 将所有纸张展开，这样每个“堆栈”中只有一张纸张。
2. 征服：
   2. 四处走动，将每张纸放在另一张纸的上面。你现在有 2 叠。
   3. 四处走动，将每个 2 堆放在另一个 2 堆上面。现在你已经有 4 叠了。
   4. 四处走动，将每个 4 堆放在另一个 4 堆之上。现在你已经有 8 叠了。
   5. ...不断地……
   6. 您现在拥有一大堆 1024 张纸！

请注意，除了计算所有内容（这不是严格必要的）之外，这是非常直观的。实际上，您可能不会一直到单页纸叠，但您可以并且它仍然有效。重要的部分是锤子：用你的手臂，你总是可以把一叠叠在另一叠上面，形成更大的一叠，并且（在合理范围内）任一叠有多大并不重要。

Answer 26

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

Answer 27

嘿，抱歉，如果我的观点同意某人，我只是想用简单的英语解释递归。

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

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

尽管您知道自己有多少个经理以及可以花费多少预算，但您永远不会知道在得到答案之前要经过多少个周期。

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

Answer 28

用简单的英语来说，递归意味着一次又一次地重复某件事。

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

看一下下面计算数字阶乘的示例：

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

Answer 29

任何算法都表现出 结构性的 数据类型的递归 if 基本上由一个 switch 语句组成，该语句针对数据类型的每种情况都有一个情况。

例如，当您正在处理一种类型时

  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

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

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

 integer = 0 | succ(integer)

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

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

著名的阶乘函数是关于此形式的最微不足道的例子。

Answer 30

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