关于计算机科学：什么是递归，什么时候应该使用它？

似乎经常在邮件列表和在线讨论中出现的主题之一是获得计算机科学学位的优点(或缺乏优点)。 反对党似乎反复提出的一个论点是，他们已经进行了多年编码，并且从未使用过递归。

所以问题是：

在此线程中有许多关于递归的很好的解释，这个答案是关于为什么不应该在大多数语言中使用它的原因。*在大多数主要的命令式语言实现中(即C，C ++，Basic，Python的每个主要实现) ，Ruby，Java和C＃)迭代远胜于递归。

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

完成所有这些步骤需要花费时间，通常比迭代循环要花费更多的时间。但是，真正的问题在于步骤1。当许多程序启动时，它们会为其堆栈分配一个内存块，并且当它们用完该内存时(通常但并非总是由于递归)，程序会由于堆栈溢出而崩溃。

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

语言实现者可以使用一种称为尾调用优化的技术，该技术可以消除某些类别的堆栈溢出。简而言之：如果函数的返回表达式只是函数调用的结果，那么您无需在堆栈上添加新级别，则可以将当前级别重用于所调用的函数。遗憾的是，几乎没有命令式语言实现内置了尾调用优化功能。

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

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

递归的简单英语示例。

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

您想找出一个链表有多长，可以通过递归来做到这一点：

(这当然也可以使用for循环来完成，但对于说明该概念很有用)

每当一个函数调用自身，创建一个循环，那么这就是递归。与任何东西一样，递归有好用和坏用。

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

但是，这是一个la脚，几乎毫无意义的示例，因为可以轻松地用更有效的迭代代替它。毕竟，递归会受到函数调用开销的影响，在上面的示例中，与函数本身内部的操作相比，递归开销很大。

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

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

如果您尝试对迭代执行相同的操作，我想您会发现需要花费更多的代码来完成。

其他常见用例可能包括遍历层次结构，例如网站搜寻器，目录比较等

结论

实际上，无论何时需要迭代分支，递归都是最有意义的。

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

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

迭代解决方案不足为奇，对于熟悉C＃的任何人都应该有意义。

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

该功能的第一部分称为基本案例(有时称为保护子句)，它是阻止算法永久运行的原因。只要调用函数的值等于或小于1，它就返回值1。第二部分更有趣，称为"递归步骤"。在这里，我们调用参数稍有修改的相同方法(将其减1)，然后将结果与n的副本相乘。

初次遇到时可能会造成混淆，因此检查运行时的工作方式很有启发性。假设我们调用FactRec(5)。我们进入了例程，没有被基本情况所接受，所以我们最终像这样：

如果我们使用参数4重新输入该方法，那么我们不会再次被Guard子句停止，因此最终结果是：

如果将这个返回值代入上面的返回值，我们得到

这应该为您提供最终解决方案的线索，因此我们将快速跟踪并显示下一个步骤：

最终替代发生在触发基本案例时。至此，我们有了一个简单的代数公式来求解，该公式首先直接等于阶乘的定义。

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

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

递归是指一种解决问题的方法，方法是解决问题的较小版本，然后使用该结果加上一些其他计算来得出原始问题的答案。通常，在解决较小版本的过程中，该方法将解决问题的较小版本，依此类推，直到达到"基本情况"为止，这是微不足道的。

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

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

In mathematics, the greatest common divisor (gcd) … of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

gcd的定义非常简单：

其中mod是取模运算符(即整数除法后的余数)。

用英语定义，该数字表示任何数字和零的最大公约数是该数字，两个数字m和n的最大公约数是n的最大公约数，以及m除以n后的余数。

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

让我们以gcd(10，8)为例进行计算。每一步都等于前一步：

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

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

递归定义往往很优雅。例如，列表总和的递归定义为

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

也许您更希望列表中的最大值：

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

如果将乘法转换为一系列加法没有意义，请尝试扩展一些简单的示例以了解其工作原理。

合并排序有一个不错的递归定义：

如果您知道要查找的内容，则到处都有递归定义。请注意，所有这些定义如何都有非常简单的基本情况，例如gcd(m，0)= m。递归案例减少了问题，以求出简单的答案。

有了这种了解，您现在就可以欣赏Wikipedia上有关递归的文章中的其他算法！

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

通常，递归不一定很快(函数调用开销往往很高，因为递归函数通常很小，请参见上文)，并且可能会遇到一些问题(堆栈溢出有人吗？)。有人说，在不平凡的情况下，他们往往很难做到"正确"，但我并不真的同意。在某些情况下，递归最有意义，并且是编写特定函数的最优雅，最清晰的方法。应该注意的是，某些语言支持递归解决方案并对其进行更多优化(想到LISP)。

递归函数是一个自行调用的函数。我发现使用它的最常见原因是遍历树结构。例如，如果我有一个带复选框的TreeView(请考虑安装新程序，"选择要安装的功能"页面)，则可能需要一个"全部选中"按钮，该按钮应如下所示(伪代码)：

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

您确实需要对递归小心一点。如果进入无限递归循环，则会出现堆栈溢出异常:)

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

我认为，因为这是一种有趣的技术，所以某些编码人员可能最终在没有实际理由的情况下经常使用该技术。这在某些圈子中给递归一个坏名字。

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

考虑将递归首字母缩略词作为一个简单示例：

• GNU代表GNU的非Unix
• PHP代表PHP：超文本预处理程序
• YAML代表YAML不是标记语言
• WINE代表Wine不是模拟器
• VISA代表Visa国际服务协会

维基百科上的更多示例

递归最适合我所谓的"分形问题"，在这种情况下，您要处理的是由较小的版本组成的大型项目，每个版本都是较小的版本，依此类推。如果您不得不遍历或搜索诸如树或嵌套的相同结构之类的东西，那么您可能会遇到问题，这可能是递归的一个不错的选择。

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

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

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

Don't use recursion for factorials or Fibonacci numbers

One problem with
computer-science textbooks is that
they present silly examples of
recursion. The typical examples are
computing a factorial or computing a
Fibonacci sequence. Recursion is a
powerful tool, and it's really dumb to
use it in either of those cases. If a
programmer who worked for me used
recursion to compute a factorial, I'd
hire someone else.

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

编辑：
这不是Dav的答案-我发布此消息时没有看到该回复

递归语句是您在其中定义下一步操作的过程的过程，该过程将输入和您已经完成的工作结合在一起。

例如，采用阶乘：

但不难发现阶乘(6)也是：

因此通常：

当然，关于递归的棘手问题是，如果您想根据已经完成的工作来定义事物，则需要有一些起点。

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

现在我们从下往上看：

因为我们定义了factorial(1)= 1，所以我们到达了"底部"。

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

1)递归部分，它根据新输入和通过相同过程"已完成"的内容定义了一些过程。 (即factorial(n) = n*factorial(n-1))

2)一个基本部分，它通过给它一定的开始位置(即factorial(1) = 1)来确保该过程不会永远重复

刚开始时可能会有些困惑，但仅查看大量示例，所有示例都应结合在一起。如果您想更深入地了解该概念，请学习数学归纳法。另外，请注意，某些语言针对递归调用进行了优化，而另一些则没有。如果您不小心的话，很容易制作出极其缓慢的递归函数，但是在大多数情况下，还有一些技巧可以使它们表现出色。

希望这可以帮助...

1.)
如果方法可以调用自身，则该方法是递归的。直接：

或间接地：

2.)何时使用递归

3.)人们仅在编写迭代代码非常复杂时才使用递归。例如，可以将树遍历技术(例如前序，后序)同时进行迭代和递归。但通常由于其简单性，我们使用递归。

这是一个简单的示例：一个集合中有多少个元素。 (有更好的计数方法，但这是一个很好的简单递归示例。)

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

假设您有一个这样的集合：[x x x]。让我们计算一下有多少个项目。

我们可以这样表示：

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

• 在此基础上，简单的案例说明了当您"用完"所有数据时会发生什么。这通常是"如果要处理的数据不足，您的答案是X"的某种变体。
• 递归规则，该规则指出如果您仍然有数据会发生什么情况。这通常是一种规则，说"做一些事情以使数据集更小，然后将规则重新应用于较小的数据集"。

如果将以上代码转换为伪代码，则会得到：

我相信还有很多更有用的示例(例如遍历一棵树)，我相信其他人会讲到。

好吧，这是一个相当不错的定义。维基百科也有一个很好的定义。因此，我将为您添加另一个(可能更糟)的定义。

人们提到"递归"时，通常是在谈论他们编写的函数，该函数会反复调用自身，直到完成其工作为止。在数据结构中遍历层次结构时，递归可能会有所帮助。

一个示例：楼梯的递归定义为：
楼梯包括：
-一步和楼梯(递归)
-或仅一步(终止)

简而言之：
假设您可以做三件事：

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

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

希望这是您正在寻找的"普通英语"答案！

这是一个古老的问题，但我想从后勤的角度(即不是从算法正确性或性能的角度)添加一个答案。

我使用Java进行工作，而Java不支持嵌套函数。这样，如果我想进行递归，则可能必须定义一个外部函数(仅由于我的代码违反了Java的官僚规则而存在)，或者我可能必须完全重构代码(我真的很讨厌这样做)。

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

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

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

考虑两个彼此面对的镜子。我们已经看到了它们产生的整洁的无限效果。每个反射都是反射镜的一个实例，该反射镜包含在另一个反射镜的实例中，依此类推。包含反射本身的反射镜就是递归。

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

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

您想在具有树形结构的任何时候使用它。在读取XML时非常有用。

计算中的递归是一种用于根据单个函数(方法，过程或块)调用的正常返回来计算结果或副作用的技术。

根据定义，递归函数必须具有直接或间接(通过其他函数)调用自身的能力，具体取决于退出条件或不满足的条件。如果满足退出条件，则特定的调用将返回到其调用方。这一直持续到返回初始调用为止，届时可获得所需的结果或副作用。

例如，这是在Scala中执行Quicksort算法的功能(从Wikipedia条目中复制为Scala)

在这种情况下，退出条件为空列表。

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

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

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

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

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

假设您有三位经理-杰克，约翰和摩根。
杰克管理着2位程序员，约翰-3位，摩根-5位。
您要给每位经理300美元，并想知道它要花多少钱。
答案很明显-但是，如果Morgan的2位员工也是经理，该怎么办？

这里是递归。
您从层次结构的顶部开始。夏季费用为0美元。
你从杰克开始
然后检查他是否有经理作为雇员。如果找到他们中的任何一个，请检查他们是否有经理作为员工，依此类推。每次您找到经理时，都要在夏季费用上加300 $。
与杰克谈完后，去找约翰，他的雇员，再去找摩根。

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

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

递归的最简单定义是"自引用"。自指的功能，即e。调用本身是递归的。要记住的最重要的一点是，递归函数必须具有"基本情况"，即e。一种条件，如果为true，则导致其不调用自身，从而终止递归。否则，您将具有无限递归：

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

如果基本上由一个开关声明以及每种数据类型的情况组成的话，任何算法都将表现出对该数据类型的结构递归。

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

结构递归算法的形式为

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

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

您会看到整数的结构递归算法如下所示

太著名的阶乘函数是关于
这种形式。

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

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

例如，如果您想获取html页面上的所有链接，则将需要递归，因为当您获取页面1上的所有链接时，您将希望获取首页上每个链接上的所有链接。那么对于到新页面的每个链接，您将需要这些链接，依此类推...换句话说，这是一个从自身内部调用自身的函数。

执行此操作时，您需要一种方法来知道何时停止，否则您将陷入无限循环，因此您需要向函数添加整数参数以跟踪循环数。

在C＃中，您将具有以下内容：

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

假设您要在字典中查找单词。您可以使用名为"查找"的操作。

您的朋友说："我现在真的可以加一些布丁！"您不知道他的意思，因此您在字典中查找"勺子"，它的内容如下：

汤匙：名词-末尾带有圆形勺的器皿。
勺子：动词-在某物上使用勺子
汤匙：动词-从后面紧紧拥抱

现在，由于您真的对英语不太熟练，因此可以为您指明正确的方向，但您需要更多信息。因此，您选择" utensil"和" cuddle"以查找更多信息。

拥抱：动词-依ugg
器具：名词-一种工具，通常是一种饮食用具

嘿!您知道什么是依ugg，与布丁无关。您还知道布丁是您要吃的东西，所以现在很有意义。您的朋友一定想用勺子吃布丁。

好的，好的，这是一个非常la脚的示例，但是它说明了(可能很差)递归的两个主要部分。
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吗？不，因此必须为4 * 3的阶乘
但是3的阶乘是多少？它是3 * 2的阶乘
2的阶乘为2 * 1的阶乘
阶乘1是1 *阶乘0
我们知道阶乘为0！ :-D为1，即定义
1的阶乘是1 * 0的阶乘是1 ...所以1 * 1 = 1
2的阶乘是2 * 1的阶乘是1 ...所以2 * 1 = 2
3的阶乘是3 * 2的阶乘是2 ...所以3 * 2 = 6
4的阶乘(最终！)是4 * 3的阶乘，即6 ... 4 * 6是24

阶乘是"基本情况，并使用其自身"的简单情况。

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

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

递归是解决大问题的一种解决问题的策略，在此过程中，每一步只是用相同的锤子"将两件小事变成一件大事"。

例

假设您的办公桌上满是乱七八糟的1024张纸。您如何使用递归从一团糟中整理出整齐干净的文件？

请注意，除了计算所有内容(并非绝对必要)之外，这非常直观。实际上，您可能不会一直走到1张纸叠，但是您可以并且仍然可以使用。重要的部分是锤子：您可以始终用胳膊将一个堆栈叠放在另一个堆栈上，以形成更大的堆栈，并且(在一定程度上)两个堆栈的大小无关紧要。

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

例如

现在可以将其递归定义为：-

用编程的术语来说，当一个函数或方法反复调用自己，直到满足某些特定条件时，此过程称为递归。但是必须有一个终止条件，并且函数或方法不得进入无限循环。

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

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

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

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

由于它非常清晰，因此很难看到它会起作用。 (非递归等效项要复杂得多，内部需要一个堆栈结构来管理要处理的事物列表。)好吧，假设当然没有人进行循环连接。

从数学上讲，显示已驯服递归的技巧是着重于找到参数大小的度量。对于我们的树示例，最简单的度量标准是树在当前节点下方的最大深度。在叶子处，它为零。在仅下面有叶子的分支上，它是一个，依此类推。然后，您可以简单地显示出，为处理树而调用该函数的参数的大小严格按照顺序排列。从度量的角度来看，递归调用的参数总是比整体调用的参数"更少"。使用严格降低的基本指标，您可以得到排序。

也可以进行无限递归。这很麻烦，并且在许多语言中都无法正常工作，因为堆栈已耗尽。 (在确实起作用的地方，语言引擎必须确定该函数某种程度上不会返回，并因此能够优化堆栈的保持。通常棘手的事情；尾递归只是实现此目的最简单的方法)

我创建了一个递归函数来连接字符串列表，并在字符串之间使用分隔符。我主要使用它来创建SQL表达式，方法是将字段列表传递为"项"，并使用"逗号+空格"作为分隔符。这是函数(它使用一些Borland Builder本机数据类型，但可以进行调整以适合任何其他环境)：

我这样称呼它：

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

随着函数开始工作，变量"结果"接收数组位置0的值，即" albumName"。

然后，它检查所处理的位置是否是最后一个。如果不是，那么它将结果与分隔符和一个函数的结果连接起来，哦，天哪，这是相同的函数。但是这一次，将其检出，它会调用自身将位置加1。

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

得到它了？如果没有，我还有另一种解释的方式。 ：o)

Mario，我不明白您为什么在该示例中使用递归。为什么不简单地遍历每个条目？像这样：

上面的方法会更快，更简单。无需使用递归代替简单的循环。我认为这些示例就是为什么递归得到不好的说唱。甚至典范阶乘函数示例也可以通过循环更好地实现。

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

因为此版本是尾递归

我使用递归。这与拥有CS学位有什么关系(顺便说一句，我不是)

我发现的常见用途：