什么是recursion，什么时候应该使用它？
似乎经常在邮件列表和在线讨论中提出的主题之一是计算机科学学位的优点（或缺乏）。 一个似乎反复出现的反对党的论点是，他们已经编了许多年，他们从来没有用过recursion。
所以问题是：
- 什么是recursion？
- 我什么时候会使用recursion？
- 为什么不使用recursion？
在这个线程中有很多关于recursion的很好的解释，这个答案是关于为什么你不应该在大多数语言中使用它。*在大多数主要的命令式语言实现（即C，C ++，Basic，Python的每个主要实现，Ruby，Java和C＃） 迭代大大优于recursion。
为了明白为什么，通过上述语言用来调用函数的步骤：
- 空间在函数的参数和局部variables的堆栈上被划分出来
- 函数的参数被复制到这个新的空间
- 控制跳转到该function
- 该函数的代码运行
- 该函数的结果被复制到一个返回值中
- 堆栈被重新回到之前的位置
- 控制跳回到函数被调用的地方
做所有这些步骤需要时间，通常比遍历循环要多一点点。 但是，真正的问题在第一步。 当许多程序启动时，它们为它们的堆栈分配一块内存，当它们耗尽内存时（通常但不总是由于recursion），由于堆栈溢出 ，程序崩溃。
所以在这些语言recursion比较慢，这使得你容易崩溃。 尽pipe如此，仍然有一些争论。 一般来说，一旦你知道如何读取代码，recursion编写的代码会更短，更优雅一些。
语言实现者可以使用一种叫做尾部调用优化的技术来消除一些栈溢出。 简单地说：如果一个函数的返回expression式只是函数调用的结果，那么不需要在堆栈中添加一个新的级别，就可以重新使用当前调用的函数。 令人遗憾的是，很less有强制性的语言实现内置了tail-call优化。
* 我喜欢recursion。 我最喜欢的静态语言根本不使用循环，recursion是重复执行某些操作的唯一方法。 我只是不认为recursion通常是一个好主意，在没有调整的语言。
**顺便说一下Mario，ArrangeString函数的典型名称是“join”，如果你select的语言还没有实现，我会感到惊讶。
简单的英文recursion的例子。
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. 在最基本的计算机科学意义上，recursion是一个自我调用的函数。 假设你有一个链表结构：
struct Node { Node* next; };
你想知道多长时间的链表，你可以做这个recursion：
int length(const Node* list) { if (!list->next) { return 1; } else { return 1 + length(list->next); } }
（这当然也可以用for循环来完成，但是作为这个概念的例子是有用的）
每当一个函数自己调用，创build一个循环，那么这是recursion。 与任何事情一样，recursion有很好的用途和不好的用途。
最简单的例子是尾recursion，函数的最后一行是对自身的调用：
int FloorByTen(int num) { if (num % 10 == 0) return num; else return FloorByTen(num-1); }
然而，这是一个蹩脚的，几乎没有意义的例子，因为它可以被更有效的迭代所取代。 毕竟，recursion受到函数调用开销的影响，在上面的例子中，与函数内部的操作相比，这可能是相当实际的。
所以做recursion而不是迭代的全部理由应该是利用调用栈来做一些聪明的事情。 例如，如果你在同一个循环中用不同的参数多次调用一个函数，那么这就是完成分支的一种方法。 一个典型的例子是谢尔宾斯基三angular形 。
你可以非常简单地用recursion来绘制其中的一个，其中调用堆栈分为三个方向：
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); } }
如果你试图用迭代来做同样的事情，我想你会发现需要更多的代码来完成。
其他常见用例可能包括遍历层次结构，例如网站爬虫，目录比较等。
结论
实际上，无论何时需要迭代分支，recursion都是最有意义的。
recursion是基于分治思维解决问题的一种方法。 其基本思想是将原始问题分解成更小的（更容易解决的）实例，解决这些较小的实例（通常再次使用相同的algorithm），然后将其重新组合成最终的解决scheme。
规范的例子是生成n的阶乘的例程。 n的阶乘通过乘以1和n之间的所有数字来计算。 C＃中的迭代解决scheme如下所示：
public int Fact(int n) { int fact = 1; for( int i = 2; i <= n; i++) { fact = fact * i; } return fact; }
迭代解决scheme没有什么奇怪的，对于熟悉C＃的人来说应该是有意义的。
recursion解决scheme是通过识别第n个因子是n *事实（n-1）find的。 换句话说，如果你知道一个特定的因子数是什么，你可以计算下一个。 这里是C＃中的recursion解决scheme：
public int FactRec(int n) { if( n < 2 ) { return 1; } return n * FactRec( n - 1 ); }
这个函数的第一部分被称为基础案例 （或者有时候是守卫子句），并且阻止algorithm永远运行。 只要函数被调用的值为1或更小，它就返回值1。 第二部分更有意思，被称为recursion步骤 。 在这里，我们调用稍微修改参数的相同方法（我们将其递减1），然后将结果与我们的n副本相乘。
当第一次遇到这种情况时可能会引起混淆，因此在运行时检查它是如何工作是有益的。 想象一下，我们称之为FactRec（5）。 我们进入日常工作，并没有被基本情况所吸收，所以我们最终这样做了：
// In FactRec(5) return 5 * FactRec( 5 - 1 ); // which is return 5 * FactRec(4);
如果我们用参数4重新input方法，我们再次不被守卫子句阻止，所以我们最终在：
// In FactRec(4) return 4 * FactRec(3);
如果我们用这个返回值代入上面的返回值，
// In FactRec(5) return 5 * (4 * FactRec(3));
这应该给你提供最终解决scheme的线索，所以我们将快速跟踪并显示每个步骤：
return 5 * (4 * FactRec(3)); return 5 * (4 * (3 * FactRec(2))); return 5 * (4 * (3 * (2 * FactRec(1)))); return 5 * (4 * (3 * (2 * (1))));
最后的替代发生在基本情况被触发时。 在这一点上，我们有一个简单的Algrebraic公式来解决这个问题，它首先等同于Factorial的定义。
注意到每个对方法的调用都会导致基本情况被触发，或者调用相同的方法（参数更靠近基本情况（通常称为recursion调用）），这是有益的。 如果情况并非如此，那么该方法将永远运行。
recursion正在解决一个调用自己的函数的问题。 一个很好的例子是一个阶乘函数。 因子是一个math问题，例如5的阶乘是5 * 4 * 3 * 2 * 1。这个函数在C＃中解决了正整数（未testing – 可能有一个错误）。
public int Factorial(int n) { if (n <= 1) return 1; return n * Factorial(n - 1); }
- 一个自己调用的函数
- 当一个函数可以（容易地）分解成一个简单的操作，并在问题的一小部分上加上相同的函数。 我应该说，相反，这使得它成为recursion的一个很好的候选者。
- 他们是这样！
典型的例子是这样的因子：
int fact(int a) { if(a==1) return 1; return a*fact(a-1); }
一般来说，recursion不一定很快（函数调用的开销往往很高，因为recursion函数往往很小，见上文），并可能遭受一些问题（堆栈溢出任何人？）。 有人说，在非平凡的情况下，他们往往很难得到“正确的”，但是我并不真正购买这些东西。 在某些情况下，recursion是最有意义的，也是编写特定函数的最优雅和最清晰的方式。 应该指出的是，有些语言更喜欢recursion的解决scheme，并优化它们（LISP的想法）。
recursion是指通过解决问题的较小版本来解决问题，然后使用该结果加上一些其他计算来形成原始问题的答案的方法。 通常，在解决小版本的过程中，该方法将解决更小版本的问题，等等，直到达到“基本情况”，这是一个微不足道的解决。
例如，要计算数字X的阶乘，可以将其表示为X times the factorial of X-1 。 因此，“recursion”的方法findX-1的阶乘，然后乘以X得到的最终答案。 当然，要findX-1的阶乘，首先要计算X-2的阶乘，依此类推。 基本情况是当X是0或1时，在这种情况下它知道从0! = 1! = 1开始返回1 0! = 1! = 1 0! = 1! = 1 0! = 1! = 1 。
考虑一个老的，众所周知的问题 ：
在math中，两个或两个以上非零整数的最大公约数 （gcd）是除数之外没有余数的最大正整数。
gcd的定义非常简单：
mod是模运算符 （即整数除法后的余数）。
在英文中，这个定义说任何数字和零的最大公约数是这个数字，两个数字m和n的最大公约数是n除以n的最大公约数。
如果你想知道为什么这个工程，请参阅维基百科有关欧几里得algorithm的文章。
我们以gcd（10,8）为例进行计算。 每一步都等于它之前的那一步：
- gcd（10，8）
- gcd（10,10模8）
- gcd（8，2）
- gcd（8，8 mod 2）
- gcd（2，0）
- 2
在第一步中，8不等于零，所以定义的第二部分适用。 10 mod 8 = 2，因为8进入10一次，余数为2.在步骤3，第二部分再次应用，但是这次8 mod 2 = 0，因为2除以8而没有余数。 在第五步，第二个参数是0，所以答案是2。
你有没有注意到gcd出现在等号的左侧和右侧？ 一个math家会说这个定义是recursion的，因为你定义的expression式在其定义里面重复出现 。
recursion定义往往是优雅的。 例如，列表的总和的recursion定义是
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
您可以recursion地定义非负整数的乘法，以将其转换为一系列的加法：
a * b = if b = 0 return 0 else return a + (a * (b - 1))
如果把乘法转换成一系列的加法是没有意义的，那么试着扩展一些简单的例子来看看它是如何工作的。
合并sorting有一个可爱的recursion定义：
sort(l) = if empty(l) or length(l) = 1 return l else (left,right) = split l return merge(sort(left), sort(right))
如果你知道要寻找什么，recursion定义是全部的。 注意所有这些定义都有非常简单的基本情况， 例如 gcd（m，0）= m。 recursion的情况削减了这个问题，以简化答案。
有了这个理解，你现在可以在维基百科关于recursion的文章中欣赏其他algorithm！
recursion函数是一个自我调用的函数。 我发现使用它的最常见的原因是遍历一个树结构。 例如，如果我有一个checkbox的TreeView（认为安装一个新的程序，“select要安装的function”页），我可能想要一个“全部检查”button，这将是这样的（伪代码）：
function cmdCheckAllClick { checkRecursively(TreeView1.RootNode); } function checkRecursively(Node n) { n.Checked = True; foreach ( n.Children as child ) { checkRecursively(child); } }
所以你可以看到checkRecursive首先检查它传递的节点，然后为每个节点的子节点调用它自己。
你需要注意recursion。 如果你进入一个无限的recursion循环，你会得到一个堆栈溢出exception:)
我想不出为什么人们不应该在适当的时候使用它。 这在某些情况下是有用的，而不是在其他情况下。
我认为，因为这是一个有趣的技术，所以有些编码者最终可能比他们应该更频繁地使用它，没有真正的理由。 这在一些圈子里给了recursion一个坏名字。
recursion最适合我所谓的“分形问题”，在这种情况下，你处理的是一个大事物的较小版本，每个事物都是一个更大的事物，等等。 如果你不得不遍历或者search类似于树或嵌套的相同结构的东西，那么你有一个问题可能是recursion的一个很好的select。
人们避免recursion的原因有很多：
-
大多数人（包括我自己）在程序或面向对象的编程方面都削减了他们的编程牙齿，而不是function编程。 对于这样的人来说，迭代方法（通常使用循环）感觉更自然。
-
我们这些削减程序或面向对象编程的编程人员经常被告知要避免recursion，因为它容易出错。
-
我们经常被告知recursion很慢。 从一个例程调用和返回重复涉及大量的堆栈推送和popup，这比循环慢。 我认为一些语言比其他语言更好地处理这些语言，而这些语言很可能不是那些主stream范式是程序性或面向对象的语言。
-
对于至less我使用过的几种编程语言，我记得听到build议，如果超出一定的深度，不会使用recursion，因为它的堆栈不够深。
recursion是直接或间接引用自身的expression式。
考虑recursion首字母缩略词作为一个简单的例子：
- GNU代表GNU的Not Unix
- PHP代表PHP：超文本预处理器
- YAML代表YAML不是标记语言
- 葡萄酒代表葡萄酒不是模拟器
- 签证代表签证国际服务协会
维基百科上的更多例子
下面是一个简单的例子：一个集合中有多less个元素。 （有更好的方法来计算事物，但这是一个很好的简单的recursion示例。）
首先，我们需要两条规则：
- 如果这个集合是空的，那么这个集合中的项目数就是零（duh！）。
- 如果该集合不是空的，则在移除一个项目之后，计数是一个加上该集合中的项目的数量。
假设你有这样一个集合：[xxx]。 让我们来算一下有多less物品。
- 该集合是非空的[xxx]，所以我们应用规则2.项目的数量是一个加上[xx]中项目的数量（即我们删除了一个项目）。
- 该集合是[xx]，所以我们再次应用规则2：一个+ [x]中的项目数量。
- 该集合是[x]，它仍然匹配规则2：一个+ []中的项目数量。
- 现在这个集合是[]，它匹配规则1：计数是零！
- 现在我们知道步骤4（0）中的答案，我们可以解决步骤3（1 + 0）
- 同样，现在我们知道步骤3（1）中的答案，我们可以解决步骤2（1 + 1）
- 最后，我们知道步骤2（2）中的答案，我们可以求解步骤1（1 + 2），并计算[xxx]中的项目数量，即3。
我们可以将其表示为：
count of [xxx] = 1 + count of [xx] = 1 + (1 + count of [x]) = 1 + (1 + (1 + count of [])) = 1 + (1 + (1 + 0))) = 1 + (1 + (1)) = 1 + (2) = 3
在应用recursion解决scheme时，通常至less有两条规则：
- 基础，这是一个简单的例子，说明当你“用完”所有的数据时会发生什么。 这通常是“如果你没有处理数据，你的答案是X”
- recursion规则，它说明如果你仍然有数据会发生什么。 这通常是某种规则，规定“尽量减less数据集，并将规则重新应用于更小的数据集”。
如果我们把上面的代码翻译成伪代码，我们得到：
numberOfItems(set) if set is empty return 0 else remove 1 item from set return 1 + numberOfItems(set)
还有更多有用的例子（例如遍历一棵树），我相信其他人会覆盖。
recursion语句就是在其中定义下一步做什么的过程，作为input和已经完成的内容的组合。
例如，采取阶乘：
factorial(6) = 6*5*4*3*2*1
但是很容易看出阶乘（6）也是：
6 * factorial(5) = 6*(5*4*3*2*1).
所以一般：
factorial(n) = n*factorial(n-1)
当然，关于recursion的棘手的事情是，如果你想用你已经完成的事情来定义事情，那么需要有一些地方可以开始。
在这个例子中，我们通过定义阶乘（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，我们达到“底部”。
一般来说，recursion程序有两个部分：
1）recursion部分，它根据新input定义了一些过程，并与通过相同过程“已经完成”的内容相结合。 （即factorial(n) = n*factorial(n-1) ）
2）一个基础部分，通过给它一些地方开始（即factorial(1) = 1 ），确保这个过程不会永远重复。
刚开始的时候可能会有些困惑，但是看一堆例子，它们应该全部结合在一起。 如果你想对这个概念有更深入的了解，可以研究math归纳法。 另外，请注意，有些语言针对recursion调用进行了优化，而另一些则没有。 如果你不小心的话，做非常慢的recursion函数是很容易的，但是在大多数情况下，也有一些技巧可以使它们成为高性能的。
希望这可以帮助…
我喜欢这个定义：
在recursion中，例程本身解决了一小部分问题，将问题分解成更小的部分，然后调用它来解决每个小部分。
我也喜欢Steve McConnells在Code Complete中对recursion的讨论，他批评了recursion计算机科学书籍中使用的例子。
不要使用阶乘或斐波那契数的recursion
计算机科学教科书的一个问题是，他们提出了recursion的愚蠢的例子。 典型的例子是计算阶乘或计算斐波那契数列。 recursion是一个强大的工具，在任何一种情况下使用它都是愚蠢的。 如果一个为我工作的程序员使用recursion来计算阶乘，我会雇用其他人。
我认为这是一个非常有趣的观点，可能是recursion经常被误解的一个原因。
编辑：这不是在Dav的答案挖 – 我没有看到这个答复，当我发布这个
1）一个方法是recursion的，如果它可以调用自己; 直接：
void f() { ... f() ... }
或间接：
void f() { ... g() ... } void g() { ... f() ... }
2.）什么时候使用recursion
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.）只有在写迭代代码非常复杂时，人们才会使用recursion。 例如，像preorder，postorder这样的树遍历技术可以做迭代和recursion。 但是通常我们使用recursion是因为它的简单性。
为了缓解一个解决的问题：什么都不做，你就完成了。
为了缓解一个公开的问题：做下一步，然后递减。
那么，这是一个相当不错的定义，你有。 维基百科也有一个很好的定义。 所以我会为你添加另一个（可能更糟糕的）定义。
当人们提到“recursion”时，他们通常会谈论自己写的一个函数，这个函数会反复调用，直到完成它的工作。 在遍历数据结构中的层次结构时，recursion会很有帮助。
一个例子：楼梯的recursion定义是：楼梯由以下几部分组成： – 单步和阶梯（recursion） – 或者只有一个步骤（终止）
用简单的英语：假设你可以做3件事情：
- 拿一个苹果
- 记下标记
- 计数标记
你桌子上有很多苹果，你想知道有多less苹果。
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
重复同样的事情，直到你完成的过程称为recursion。
我希望这是你正在寻找的“简单英语”的答案！
recursion函数是一个包含对自身的调用的函数。 recursion结构是包含自身实例的结构。 你可以把这两个结合起来作为recursion类。 recursion项的关键部分是它包含一个实例/它自己的调用。
考虑两个面对面的镜子。 我们已经看到了他们所做的整洁的无限效果。 每个reflection都是镜像的一个实例，它包含在另一个镜像实例中，等等。包含自身reflection的镜像是recursion的。
二叉search树是recursion的一个很好的编程例子。 该结构是recursion的，每个节点包含2个节点的实例。 在二叉search树上工作的函数也是recursion的。
这是一个古老的问题，但我想从逻辑的angular度（即不是从algorithm正确性的angular度或性能的angular度来看）添加一个答案。
我使用Java进行工作，Java不支持嵌套function。 因此，如果我想做recursion，我可能不得不定义一个外部函数（这只是因为我的代码碰到了Java的官僚规则），否则我可能不得不重构代码（我真的不想这样做）。
因此，我经常避免recursion，而是使用堆栈操作，因为recursion本身本质上是一个堆栈操作。
你想在任何时候使用它，你有一个树结构。 这在读取XML时非常有用。
它适用于编程的recursion基本上是从它自己的定义（在它自己内部）中用不同的参数来调用一个函数，以完成一个任务。
“如果我有一把锤子，把所有东西看起来都像钉子一样。”
recursion是解决巨大问题的一种解决问题的策略，每一步都要用同一把锤子“把两件小东西变成一件大事”。
例
假设你的办公桌被1024张纸杂乱无章地覆盖着。 你如何使用recursion方法从乱七八糟的文件中整理一堆干净的文件？
- 划分：将所有的工作表分开，因此每个“堆栈”中只有一个工作表。
- 征服：
- 转过身来，把每张纸放在另一张纸的上面。 你现在有2个堆栈。
- 回过头来，把每个2堆栈放在另一个堆栈的顶部。 你现在有4堆。
- 转过身来，把每个4层叠放在另一个4层叠层之上。 你现在有8个堆栈。
- …继续…
- 你现在有一个巨大的1024张纸堆！
注意这很直观，除了计算一切（这不是绝对必要的）。 实际上，你可能不会一路走到一张纸堆上，但是你可以并且仍然能够工作。 重要的部分是锤子：用你的arm，你总是可以把一个堆叠放在另一个的上面，做出一个更大的堆叠，这个堆叠有多大也没有关系。
recursion是一个方法调用自己能够执行某个任务的过程。 它减less了代码的重复。 大多数recursion函数或方法都必须有一个限制来打破callback调用，即如果条件满足，就不要调用它自己 – 这可以防止创build无限循环。 并不是所有的函数都适合recursion使用。
嘿，对不起，如果我的意见同意某人，我只是试图用简单的英文解释recursion。
假设你有三个经理 – 杰克，约翰和摩根。 杰克pipe理2名程序员，约翰 – 3和摩根 – 5。你将会给每个经理300美元，并想知道它会花多less钱。 答案是显而易见的 – 但如果摩根员工中的两名也是经理呢？
这里是recursion。 你从层次结构的顶部开始。 总结成本是0 $。 你从杰克开始，然后检查他是否有任何经理作为雇员。 如果你发现他们中的任何一个，检查他们是否有任何经理作为雇员等等。 每次find一位经理时，加上300美元的总和费用。 当你完成杰克，去约翰，他的员工，然后到摩根。
你永远不会知道，在得到答案之前，你会花多less周期去做，尽pipe你知道你有多lesspipe理者，你可以花多less预算。
recursion是一棵树，有树枝和树叶，分别称为父母和孩子。 当你使用recursionalgorithm时，你或多或less有意识地从数据中构build一棵树。
用简单的英语，recursion意味着一次又一次地重复。
在编程中，一个例子是在其内部调用函数。
请看以下计算数字阶乘的例子：
public int fact(int n) { if (n==0) return 1; else return n*fact(n-1) }
任何algorithm都对数据types展示结构recursion，如果基本上由一个switch-statement组成，并且每个case数据types都有一个case。
例如，当你在一个types的工作
tree = null | leaf(value:integer) | node(left: tree, right:tree)
结构recursionalgorithm将具有这种forms
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
这实际上是编写任何适用于数据结构的algorithm的最明显的方法。
现在，当你看到使用Peano公理定义的整数（以及自然数）时
integer = 0 | succ(integer)
you see that a structural recursive algorithm on integers looks like this
function computeSomething(x : integer) = if x is 0 : base case if x is succ(prev) : do something with prev
the too-well-known factorial function is about the most trivial example of this form.
function call itself or use its own definition.
