什么是递归，什么时候应该使用它？

1. 调用自身的函数
2. 当一个函数可以(容易地)分解成一个简单的操作，再加上同一个函数的一些较小的部分的问题。我应该说，这使它成为递归的一个很好的候选者。
3. 是的！

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

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


return a*fact(a-1);
}

In general, recursion isn't necessarily fast (function call overhead tends to be high because recursive functions tend to be small, see above) and can suffer from some problems (stack overflow anyone?). Some say they tend to be hard to get 'right' in non-trivial cases but I don't really buy into that. In some situations, recursion makes the most sense and is the most elegant and clear way to write a particular function. It should be noted that some languages favor recursive solutions and optimize them much more (LISP comes to mind).

递归函数是一个调用自己的函数。我发现使用它最常见的原因是遍历树结构。例如，如果我有一个带复选框的 TreeView (想想安装一个新程序，“选择要安装的特性”页面) ，我可能想要一个“全部选中”按钮，类似下面这样(伪代码) :

function cmdCheckAllClick {
checkRecursively(TreeView1.RootNode);
}


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

所以您可以看到 checkRecursive 首先检查传递给它的节点，然后为该节点的每个子节点调用自己。

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

我想不出人们为什么不能在适当的时候使用它。它在某些情况下是有用的，而在其他情况下则不然。

I think that because it's an interesting technique, some coders perhaps end up using it more often than they should, without real justification. This has given recursion a bad name in some circles.

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

The canonical example is a routine to generate the Factorial of n. The Factorial of n is calculated by multiplying all of the numbers between 1 and n. An iterative solution in C# looks like this:

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。第二部分更有趣，被称为 递归步骤。这里我们用一个稍微修改过的参数调用相同的方法(我们将它减1) ，然后将结果与 n 的副本相乘。

当第一次遇到这种情况时，可能会有些困惑，所以检查一下它在运行时是如何工作的是很有启发性的。假设我们调用 FactRec (5)。我们进入例行程序，没有被基本情况所接受，所以我们的结局是这样的:

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


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

如果我们使用参数4重新输入方法，我们仍然没有被 Guard 子句停止，因此我们最终得到:

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

If we substitute this return value into the return value above we get

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

That final substitution happens when the base case is triggered. At this point we have a simple algrebraic formula to solve which equates directly to the definition of Factorials in the first place.

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

我已经创建了一个递归函数，用于在字符串列表之间连接一个分隔符。我主要使用它来创建 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, ", ");

假设您有一个名为‘ 田野’的数组，其中包含以下数据: ‘ 专辑名称’、‘ releaseDate’、‘ LabelId’。然后调用函数:

ArrangeString(fields, 0, ", ");

As the function starts to work, the variable '结果' receives the value of the position 0 of the array, which is '专辑名称'.

然后它检查它处理的位置是否是最后一个。因为它不是，所以它把结果和分隔符连接起来还有一个函数的结果，天哪，就是这个函数。但是这一次，检查一下，它称自己为位置加1。

ArrangeString(fields, 1, ", ");

它不断地重复，创建一个 LIFO 堆，直到它到达一个点，在这个点上被处理的位置是最后一个，所以函数只返回列表中该位置上的项，不再连接。然后这一堆向后连接。

明白了吗? 如果你不明白，我有另一种方法来解释

递归在我称之为“分形问题”的情况下表现得最好，在这种情况下，你要处理的是一个由大问题的小版本组成的大问题，每个小版本都是大问题的更小版本，等等。如果您需要遍历或搜索类似树或嵌套相同结构的内容，那么您遇到的问题可能是递归的一个很好的候选者。

人们避免递归有以下几个原因:

1. 大多数人(包括我自己)都是从过程或面向对象程序设计开始编程的，而不是函数式编程。对于这些人来说，迭代方法(通常使用循环)感觉更自然。

2. 我们这些在过程或者面向对象程序设计上初学编程的人经常被告知要避免递归，因为它容易出错。

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

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

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

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

1. 如果集合为空，则集合中的项计数为零(当然!)。
2. 如果集合不为空，则计数为1加上删除一个项后集合中的项数。

假设你有一个这样的集合: [ x x x ]。让我们来计算有多少项。

1. 集合是[ x x x ] ，它不是空的，所以我们应用规则2。项目数是1加上[ x x ]中的项目数(即我们删除了一个项目)。
2. the set is [x x], so we apply rule 2 again: one + number of items in [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

在应用递归解决方案时，您通常至少有两条规则:

• 基础，简单的情况下，说明什么发生时，你已经“用完”了你的所有数据。这通常是“如果你没有数据要处理，你的答案是 X”的变体
• the recursive rule, which states what happens if you still have data. This is usually some kind of rule that says "do something to make your data set smaller, and reapply your rules to the smaller data set."

如果我们将上面的代码转换为伪代码，我们得到:

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

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

我用递归。这和 CS 学位有什么关系... (顺便说一句，我没有)

Common uses I have found:

1. Sitemaps -从文档根开始通过文件系统递归
2. 蜘蛛 -在网站中搜索电子邮件地址、链接等。
3. ?

Mario, I don't understand why you used recursion for that example.. Why not simply loop through each entry? Something like this:

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

上述方法更快，也更简单。没有必要用递归代替简单的循环。我认为这些例子就是为什么递归不受欢迎的原因。甚至规范的阶乘函数示例也可以用循环更好地实现。

对已解决的问题进行递归: 什么也不做，就完成了。
To recurse on an open problem: do the next step, then recurse on the rest.

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

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

1. 在 the stack上为函数的参数和局部变量划出空间
2. 函数的参数被复制到这个新的空间中
3. control jumps to the function
4. 函数的代码运行
5. 函数的结果被复制到一个返回值中
6. 堆栈被重新回到它之前的位置
7. 控件跳回到函数被调用的位置

执行所有这些步骤都需要花费时间，通常比循环迭代所需的时间略多一点。然而，真正的问题在于步骤 # 1。当许多程序启动时，它们为堆栈分配单个内存块，当它们耗尽该内存(通常，但并非总是由于递归)时，程序会因为 堆栈溢出堆栈溢出崩溃。

所以在这些语言中递归比较慢，容易崩溃。尽管如此，仍然有一些关于使用它的争论。一般来说，一旦您知道如何阅读递归编写的代码，它会更短并且更优雅一些。

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

* 我喜欢递归。我最喜欢的静态语言根本不使用循环，递归是重复做某事的唯一方法。我只是不认为递归在不适合它的语言中是一个好主意。

顺便说一下，Mario，您所选择的编程语言的典型名称是“ join”，如果您的编程语言还没有实现它的话，我会感到惊讶的。

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

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

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

因为这个版本是 尾巴递归

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

struct Node {
Node* next;
};

你想知道一个链表有多长你可以用递归算出来:

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

(这当然也可以用 for 循环来完成，但是可以作为概念的说明)

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

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

For instance, to calculate a factorial for the number X, one can represent it as X times the factorial of X-1. Thus, the method "recurses" to find the factorial of X-1, and then multiplies whatever it got by X to give a final answer. Of course, to find the factorial of X-1, it'll first calculate the factorial of X-2, and so on. The base case would be when X is 0 or 1, in which case it knows to return 1 since 0! = 1! = 1.

你的定义还真不错。维基百科也有一个很好的定义。因此，我将为您添加另一个(可能更糟糕的)定义。

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

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

我也喜欢 Steve McConnells 在《代码完成》中关于递归的讨论，他批评了计算机科学书籍中关于递归的例子。

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

有一个问题 计算机科学教科书就是 他们提出愚蠢的例子 典型的例子有 计算阶乘或计算 斐波那契数列，递归是 强大的工具，它真的很愚蠢 在这两种情况下都可以使用 为我工作的程序员 递归来计算阶乘，I’d 雇别人吧。

我认为这是一个非常有趣的观点，也许这就是为什么递归经常被误解的原因。

编辑: This was not a dig at Dav's answer - I had not seen that reply when I posted this

递归是用一个调用自身的函数来解决问题。一个很好的例子是阶乘函数。阶乘是一个数学问题，其中阶乘5，例如，是5 * 4 * 3 * 2 * 1。这个函数在 C # 中为正整数解决了这个问题(没有测试——可能有 bug)。

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


return n * Factorial(n - 1);
}

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

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

例子

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

1. 分割: 将所有的工作表展开，这样你在每个“堆栈”中只有一个工作表。
2. 2. 绕过去，把每张纸叠在另一张纸上，你现在有了两叠纸。
   3. 绕过去，把每个2层叠放在另一个2层叠的上面。你现在有4层叠了。
   4. 绕过去，把每个4层叠放在另一个4层叠的上面。你现在有8层叠了。
   5. ... on and on ...
   6. 你现在有一个巨大的1024张纸的堆栈！

• GNU 代表 GNU 的 Not Unix
• PHP 代表 < strong > PHP: PHP
• YAML 代表 < strong > YAML Ain’t Markup Language
• WINE 代表的是 < strong > WINE Is Not an Simulator (葡萄酒不是模拟器)
• VISA 代表 < strong > VISA 国际服务协会

维基百科上的更多例子

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

例如，如果你想得到一个 html 页面上的所有链接，你需要递归，因为当你得到第一页上的所有链接时，你需要得到第一页上的每个链接上的所有链接。然后对于一个新页面的每个链接，你会想要这些链接等等... ... 换句话说，它是一个从内部调用自己的函数。

当你这样做的时候，你需要一种方法来知道什么时候停止，否则你将在一个无止境的循环，所以你添加一个整数参数的函数来跟踪周期的数量。

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

Recursion is the process where a method call iself to be able to perform a certain task. It reduces redundency of code. Most recurssive functions or methods must have a condifiton to break the recussive call i.e. stop it from calling itself if a condition is met - this prevents the creating of an infinite loop. Not all functions are suited to be used recursively.

In plain English, recursion means to repeat someting again and again.

在编程中，一个例子是调用函数本身。

看看下面计算一个数的阶乘的例子:

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

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

假设你有三个经理——杰克、约翰和摩根。 Jack manages 2 programmers, John - 3, and Morgan - 5. 你会给每个经理300美元，并想知道它的成本。 The answer is obvious - but what if 2 of Morgan-s employees are also managers?

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

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

Recursion is a tree, with branches and leaves, called parents and children respectively. 当您使用递归算法时，您或多或少是有意识地从数据中构建一棵树。

简单地说: 假设你可以做三件事:

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

重复同样的事情直到完成的过程叫做递归。

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

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

例如，以阶乘为例:

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

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

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

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

2)一个基本部分，通过给它一个开始的地方(比如 factorial(1) = 1)来确保过程不会永远重复

一开始你可能会觉得有点困惑，但是只要看一些例子，你就会明白。如果你想对这个概念有更深入的理解，那就学习数学归纳法。另外，请注意，有些语言针对递归调用进行了优化，而其他语言则没有。如果不小心的话，很容易创建速度非常慢的递归函数，但是在大多数情况下，也有一些技术可以使它们具有高性能。

希望这个能帮上忙。

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

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

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

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

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

您可以使用递归来绘制其中的一个，其中调用堆栈分为三个方向:

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

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

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

结论

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

例如: 楼梯的递归定义是: 楼梯由以下部分组成: 一个台阶和一个楼梯(递归) - 或者只是一个步骤(终止)

Any algorithm exhibits 结构性的 recursion on a datatype if basically consists of a switch-statement with a case for each case of the datatype.

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

  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

众所周知的阶乘函数是关于 这张表格。

Consider an 众所周知的老问题:

In mathematics, the 最大公约数 (gcd) … of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

Gcd 的定义出人意料地简单:

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

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

如果您想知道为什么这样做，请参阅关于 辗转相除法的维基百科文章。

让我们以 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不等于零，因此应用定义的第二部分。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。递归案例逐渐减少了问题的复杂性，最终得到了简单的答案。

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

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

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

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

例如，这里有一个函数用于在 Scala (复制自 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)
}

In this case the exit condition is an empty list.

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

比如说

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

现在它可以递归地定义为:-

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

In programming terms, when a function or method calls itself repeatedly, until some specific condition gets satisfied, this process is called Recursion. But there must be a terminating condition and function or method must no enter into an infinite loop.

A great many problems can be thought of in two types of pieces:

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

很容易就能看出来这个办法行得通，因为这是显而易见的。(非递归等价物要复杂得多，需要在内部使用堆栈结构来管理要处理的事物列表。)当然，前提是没人做过循环连接。

在数学上，显示递归被驯服的诀窍是集中精力寻找参数大小的度量。对于我们的树示例，最简单的度量是当前节点下的树的最大深度。在树叶上，是零。在只有叶子的树枝上，它是一个，等等。然后，您可以简单地展示，为了处理树，函数调用的参数的大小是严格有序的; 递归调用的参数在度量意义上总是“小于”整体调用的参数。使用严格递减的基数度量，可以进行排序。

无限递归也是可能的。这很混乱，而且在许多语言中不会起作用，因为堆栈会爆炸。(当它工作时，语言引擎必须确定函数不会以某种方式返回，因此能够优化堆栈的保持。一般来说，这是一个棘手的问题; 尾递归只是实现这一点的最简单的方法。)

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

假设你想在字典里查一个单词。你有一个叫做“查询”的任务。

你的朋友说“我现在真想吃点布丁!”你不知道他是什么意思，所以你在字典里查找“勺子”，它读起来是这样的:

勺子: 名词-末端有一个圆形勺子的器具。 勺子: 动词-在某物上使用勺子 勺子: 动词-从后面紧紧拥抱

现在，由于你真的不擅长英语，这为你指出了正确的方向，但你需要更多的信息。所以你选择“用具”和“拥抱”来查找更多信息。

依偎: 动词——依偎 Utensil: noun - a tool, often an eating utensil

嘿！你知道什么是依偎，而且跟布丁没关系。你也知道布丁是你吃的东西，所以现在说得通了。你的朋友肯定想用勺子吃布丁。

好吧，好吧，这是一个非常蹩脚的例子，但是它说明了递归的两个主要部分(也许很糟糕)。 1)自我利用。在这个示例中，在理解一个单词之前，您并没有真正查找过有意义的单词，这可能意味着查找更多的单词。这就引出了第二点, 2)它会在某个地方停下来。它必须有某种基础。否则，你最终只能查字典里的每一个单词，这可能不太有用。我们的基本情况是，你得到了足够的信息，使之之间的联系，你以前做了什么和不明白。

给出的传统示例是 factorial，其中5 factorial 是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的阶乘? 它是2的3 * 阶乘 2的阶乘是1的2 * 阶乘 1的阶乘为1 * 的阶乘为0 我们知道阶乘为0! :-D 是1，这就是定义 1的阶乘是0的1 * 阶乘，也就是1... 所以1 * 1 = 1 阶乘2是2 * 阶乘1也就是1... 所以2 * 1 = 2 3的阶乘是2的3 * 阶乘，也就是2... 所以3 * 2 = 6 Factorial of 4(finally!)是4 * factorial of 3，也就是6... 4 * 6是24

Factorial 是一个简单的“基本情况，并使用自己”的情况。

现在，注意我们仍然在整个下降过程中处理阶乘4... ... 如果我们想要阶乘100，我们必须一直下降到0... ... 这可能会有很多开销。同样地，如果我们在字典里找到一个晦涩难懂的单词，可能需要查找其他单词和上下文线索，直到找到一个我们熟悉的联系。递归方法可能需要很长时间才能完成。然而，当它们被正确地使用和理解时，它们可以使复杂的工作出奇地简单。

递归最简单的定义是“自引用”。引用自己的函数，即调用自己的函数是递归的。需要记住的最重要的一点是，递归函数必须有一个“基本情况”，即一个条件，如果为真，它就不会调用自己，从而终止递归。否则就会有无限递归:

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

递归的简单英语例子。

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.

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

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

二叉查找树是一个很好的递归编程示例。该结构是递归的，每个 Node 包含一个 Node 的2个实例。处理二叉查找树的函数也是递归的。

A method is recursive if it can call itself; either directly:

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

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

我在工作中使用 Java，而 Java 不支持嵌套函数。因此，如果我想做递归，我可能必须定义一个外部函数(它的存在只是因为我的代码与 Java 的官僚规则相冲突) ，或者我可能必须重构所有的代码(我真的很讨厌这么做)。

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