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

One of the topics that seems to come up regularly on mailing lists and online discussions is the merits (or lack thereof) of doing a Computer Science Degree. An argument that seems to come up time and again for the negative party is that they have been coding for some number of years and they have never used recursion.

在邮件列表和在线讨论中经常出现的一个主题是计算机科学学位的优点(或缺乏)。一个似乎一再出现的观点是，对于消极方来说，他们已经编码多年了，而且从来没有使用过递归。

So the question is:

所以问题是:

1. What is recursion?
2. 递归是什么?
3. When would I use recursion?
4. 什么时候使用递归?
5. Why don't people use recursion?
6. 为什么人们不使用递归呢?

40 个解决方案

#1

There are a number of good explanations of recursion in this thread, this answer is about why you shouldn't use it in most languages.* In the majority of major imperative language implementations (i.e. every major implementation of C, C++, Basic, Python, Ruby,Java, and C#) iteration is vastly preferable to recursion.

在这个线程中有许多关于递归的很好的解释，这就是为什么在大多数语言中不应该使用它的原因。*在大多数命令式语言实现中(例如，C、c++、Basic、Python、Ruby、Java和c#的每个主要实现)，迭代要比递归好得多。

To see why, walk through the steps that the above languages use to call a function:

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

1. space is carved out on the stack for the function's arguments and local variables
2. 在堆栈上为函数的参数和局部变量划分空间
3. the function's arguments are copied into this new space
4. 函数的参数被复制到这个新空间中
5. control jumps to the function
6. 控件跳转到函数
7. the function's code runs
8. 函数的代码运行
9. the function's result is copied into a return value
10. 函数的结果被复制到返回值中
11. the stack is rewound to its previous position
12. 堆栈被重绕到先前的位置
13. control jumps back to where the function was called
14. 控件跳转回函数调用的位置

Doing all of these steps takes time, usually a little bit more than it takes to iterate through a loop. However, the real problem is in step #1. When many programs start, they allocate a single chunk of memory for their stack, and when they run out of that memory (often, but not always due to recursion), the program crashes due to a stack overflow.

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

So in these languages recursion is slower and it makes you vulnerable to crashing. There are still some arguments for using it though. In general, code written recursively is shorter and a bit more elegant, once you know how to read it.

在这些语言中，递归比较慢，很容易崩溃。尽管如此，仍然有一些使用它的理由。一般来说，当你知道如何读取代码时，递归的代码会更短，更优雅。

There is a technique that language implementers can use called tail call optimization which can eliminate some classes of stack overflow. Put succinctly: if a function's return expression is simply the result of a function call, then you don't need to add a new level onto the stack, you can reuse the current one for the function being called. Regrettably, few imperative language-implementations have tail-call optimization built in.

有一种语言实现者可以使用的技术叫做尾调用优化，它可以消除一些类的堆栈溢出。言简意赅地说:如果函数的返回表达式仅仅是函数调用的结果，那么您不需要在堆栈中添加一个新级别，您可以为被调用的函数重用当前的级别。遗憾的是，几乎没有必要的语言实现内置了尾部调用优化。

* I love recursion. My favorite static language doesn't use loops at all, recursion is the only way to do something repeatedly. I just don't think that recursion is generally a good idea in languages that aren't tuned for it.

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

** By the way Mario, the typical name for your ArrangeString function is "join", and I'd be surprised if your language of choice doesn't already have an implementation of it.

顺便说一下，Mario，你的ArrangeString函数的典型名字是“join”，如果你选择的语言没有实现它，我会很惊讶。

#2

Simple english example of 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.

#3

In the most basic computer science sense, recursion is a function that calls itself. Say you have a linked list structure:

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

struct Node {
    Node* next;
};

And you want to find out how long a linked list is you can do this with recursion:

你想知道一个链表能递归多久

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

(This could of course be done with a for loop as well, but is useful as an illustration of the concept)

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

#4

Whenever a function calls itself, creating a loop, then that's recursion. As with anything there are good uses and bad uses for recursion.

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

The most simple example is tail recursion where the very last line of the function is a call to itself:

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

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

However, this is a lame, almost pointless example because it can easily be replaced by more efficient iteration. After all, recursion suffers from function call overhead, which in the example above could be substantial compared to the operation inside the function itself.

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

So the whole reason to do recursion rather than iteration should be to take advantage of the call stack to do some clever stuff. For example, if you call a function multiple times with different parameters inside the same loop then that's a way to accomplish branching. A classic example is the Sierpinski triangle.

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

You can draw one of those very simply with recursion, where the call stack branches in 3 directions:

你可以用递归很简单地画出其中的一个，其中调用堆栈在三个方向上分支:

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

If you attempt to do the same thing with iteration I think you'll find it takes a lot more code to accomplish.

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

Other common use cases might include traversing hierarchies, e.g. website crawlers, directory comparisons, etc.

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

Conclusion

结论

In practical terms, recursion makes the most sense whenever you need iterative branching.

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

#5

Recursion is a method of solving problems based on the divide and conquer mentality. The basic idea is that you take the original problem and divide it into smaller (more easily solved) instances of itself, solve those smaller instances (usually by using the same algorithm again) and then reassemble them into the final solution.

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

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:

典型的例子是生成n的阶乘的例行程序。n的阶乘是通过将1和n之间的所有数字相乘来计算的。

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

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

  return fact;
}

There's nothing surprising about the iterative solution and it should make sense to anyone familiar with C#.

迭代解决方案没什么好奇怪的，对熟悉c#的人来说应该是有意义的。

The recursive solution is found by recognising that the nth Factorial is n * Fact(n-1). Or to put it another way, if you know what a particular Factorial number is you can calculate the next one. Here is the recursive solution in C#:

通过认识到第n的阶乘是n * Fact(n-1)，可以找到递归解。或者换一种说法，如果你知道一个特定的阶乘数是多少你可以计算下一个。下面是c#中的递归解决方案:

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

  return n * FactRec( n - 1 );
}

The first part of this function is known as a Base Case (or sometimes Guard Clause) and is what prevents the algorithm from running forever. It just returns the value 1 whenever the function is called with a value of 1 or less. The second part is more interesting and is known as the Recursive Step. Here we call the same method with a slightly modified parameter (we decrement it by 1) and then multiply the result with our copy of n.

这个函数的第一部分被称为基本情况(有时是保护子句)，它阻止算法永远运行。只要函数调用值为1或更小，它就返回值1。第二部分更有趣，称为递归步骤。这里我们用一个稍微修改过的参数调用相同的方法(我们将其递减1)然后将结果与我们的n拷贝相乘。

When first encountered this can be kind of confusing so it's instructive to examine how it works when run. Imagine that we call FactRec(5). We enter the routine, are not picked up by the base case and so we end up like this:

当第一次遇到这种情况时，可能会有点困惑，因此在运行时检查它是如何工作的很有意义。假设我们调用FactRec(5)我们进入常规，不被基本情况所接受，所以我们的结局是这样的:

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

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

If we re-enter the method with the parameter 4 we are again not stopped by the guard clause and so we end up at:

如果我们用参数4重新输入方法，我们又不会被保护条款阻止，所以我们在:

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

This should give you a clue as to how the final solution is arrived at so we'll fast track and show each step on the way down:

这应该会给你一个关于最终解决方案是如何得出的线索，所以我们将快速跟踪并展示在下降的过程中的每一步:

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.

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

It's instructive to note that every call into the method results in either a base case being triggered or a call to the same method where the parameters are closer to a base case (often called a recursive call). If this is not the case then the method will run forever.

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

#6

Recursion is solving a problem with a function that calls itself. A good example of this is a factorial function. Factorial is a math problem where factorial of 5, for example, is 5 * 4 * 3 * 2 * 1. This function solves this in C# for positive integers (not tested - there may be a bug).

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

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

    return n * Factorial(n - 1);
}

#7

1. A function that calls itself
2. 一个调用自身的函数
3. When a function can be (easily) decomposed into a simple operation plus the same function on some smaller portion of the problem. I should say, rather, that this makes it a good candidate for recursion.
4. 当一个函数可以(容易地)分解成一个简单的操作，并在问题的较小部分上使用相同的函数时。我应该说，这使它成为一个很好的递归候选。
5. They do!
6. 他们做的!

The canonical example is the factorial which looks like:

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

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).

一般来说，递归并不一定很快(函数调用开销往往很高，因为递归函数往往很小，请参阅上面的内容)，并且可能会遇到一些问题(栈溢出谁?)有些人说，在非平凡的情况下，他们往往很难做到“正确”，但我并不真正认同这一点。在某些情况下，递归是最有意义的，是编写特定函数的最优雅、最清晰的方法。应该注意的是，有些语言更喜欢递归解决方案，并对它们进行更多的优化(我想到了LISP)。

#8

Recursion refers to a method which solves a problem by solving a smaller version of the problem and then using that result plus some other computation to formulate the answer to the original problem. Often times, in the process of solving the smaller version, the method will solve a yet smaller version of the problem, and so on, until it reaches a "base case" which is trivial to solve.

递归是一种解决问题的方法，它通过解决问题的一个较小的版本，然后使用这个结果和一些其他的计算来表达原始问题的答案。通常情况下，在解决较小版本的过程中，该方法将解决更小版本的问题，等等，直到达到一个“基本情况”，这个“基本情况”很难解决。

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.

例如，要计算X的阶乘，可以用X乘以X-1的阶乘来表示。因此，这个方法“递归”来找到X-1的阶乘，然后乘以X得到的任何数，得到最终的答案。当然，要找到X-1的阶乘，它首先计算X-2的阶乘，等等。基本情况是当X为0或1时，在这种情况下，它知道从0返回1 != 1 != 1。

#9

Consider an old, well known problem:

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

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)，是最大的正整数，它把数字除以没有余数。

The definition of gcd is surprisingly simple:

gcd的定义非常简单:

where mod is the modulo operator (that is, the remainder after integer division).

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

In English, this definition says the greatest common divisor of any number and zero is that number, and the greatest common divisor of two numbers m and n is the greatest common divisor of n and the remainder after dividing m by n.

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

If you'd like to know why this works, see the Wikipedia article on the Euclidean algorithm.

如果你想知道为什么会这样，请参阅*上关于Euclidean算法的文章。

Let's compute gcd(10, 8) as an example. Each step is equal to the one just before it:

让我们以gcd(10,8)为例进行计算。每一步都等于前面的一步:

1. gcd(10, 8)
2. 肾小球囊性肾病(10、8)
3. gcd(10, 10 mod 8)
4. 肾小球囊性肾病(10,国防部8)
5. gcd(8, 2)
6. 肾小球囊性肾病(8,2)
7. gcd(8, 8 mod 2)
8. 肾小球囊性肾病(8,8国防部2)
9. gcd(2, 0)
10. 肾小球囊性肾病(2,0)
11. 2
12. 2

In the first step, 8 does not equal zero, so the second part of the definition applies. 10 mod 8 = 2 because 8 goes into 10 once with a remainder of 2. At step 3, the second part applies again, but this time 8 mod 2 = 0 because 2 divides 8 with no remainder. At step 5, the second argument is 0, so the answer is 2.

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

Did you notice that gcd appears on both the left and right sides of the equals sign? A mathematician would say this definition is recursive because the expression you're defining recurs inside its definition.

你注意到gcd出现在等号的左边和右边吗?数学家会说这个定义是递归的，因为你定义的表达式会在它的定义中重复出现。

Recursive definitions tend to be elegant. For example, a recursive definition for the sum of a list is

递归定义趋向于优雅。例如，列表和的递归定义是

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

where head is the first element in a list and tail is the rest of the list. Note that sum recurs inside its definition at the end.

head是列表中的第一个元素，tail是列表的其余部分。请注意，求和在它的定义中在末尾重复出现。

Maybe you'd prefer the maximum value in a list instead:

也许你更喜欢列表中的最大值:

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

You might define multiplication of non-negative integers recursively to turn it into a series of additions:

你可以递归地定义非负整数的乘法，把它变成一系列的加法:

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

If that bit about transforming multiplication into a series of additions doesn't make sense, try expanding a few simple examples to see how it works.

如果把乘法变换成一系列的加法没有意义，可以尝试扩展几个简单的例子，看看它是如何工作的。

Merge sort has a lovely recursive definition:

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

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

Recursive definitions are all around if you know what to look for. Notice how all of these definitions have very simple base cases, e.g., gcd(m, 0) = m. The recursive cases whittle away at the problem to get down to the easy answers.

如果你知道要寻找什么，递归定义就会出现。注意，所有这些定义都有非常简单的基本情况，例如，gcd(m, 0) = m。

With this understanding, you can now appreciate the other algorithms in Wikipedia's article on recursion!

有了这样的理解，您现在可以欣赏*关于递归的文章中的其他算法了!

#10

A recursive function is one which calls itself. The most common reason I've found to use it is traversing a tree structure. For example, if I have a TreeView with checkboxes (think installation of a new program, "choose features to install" page), I might want a "check all" button which would be something like this (pseudocode):

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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

So you can see that the checkRecursively first checks the node which it is passed, then calls itself for each of that node's children.

因此，您可以看到，check递归首先检查它所传递的节点，然后调用该节点的每个子节点。

You do need to be a bit careful with recursion. If you get into an infinite recursive loop, you will get a Stack Overflow exception :)

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

I can't think of a reason why people shouldn't use it, when appropriate. It is useful in some circumstances, and not in others.

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

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.

我认为，因为这是一种有趣的技术，一些程序员可能会比他们应该的更经常地使用它，而没有真正的理由。这给递归带来了坏名声。

#11

Recursion works best with what I like to call "fractal problems", where you're dealing with a big thing that's made of smaller versions of that big thing, each of which is an even smaller version of the big thing, and so on. If you ever have to traverse or search through something like a tree or nested identical structures, you've got a problem that might be a good candidate for recursion.

递归最适用于我称之为“分形问题”的问题，在这个问题中，你要处理的是一个大问题，这个大问题的小版本，每个小版本都是这个大问题的小版本，以此类推。如果您需要遍历或搜索树或嵌套的相同结构，您就会遇到一个问题，这可能是递归的一个很好的候选者。

People avoid recursion for a number of reasons:

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

1. Most people (myself included) cut their programming teeth on procedural or object-oriented programming as opposed to functional programming. To such people, the iterative approach (typically using loops) feels more natural.

   大多数人(包括我自己)在程序化或面向对象编程上(而不是函数式编程)减少了编程接口。对于这些人来说，迭代方法(通常使用循环)感觉更自然。

2. Those of us who cut our programming teeth on procedural or object-oriented programming have often been told to avoid recursion because it's error prone.

   我们中那些在程序或面向对象编程上减少编程的人经常被告知避免递归，因为它容易出错。

3. We're often told that recursion is slow. Calling and returning from a routine repeatedly involves a lot of stack pushing and popping, which is slower than looping. I think some languages handle this better than others, and those languages are most likely not those where the dominant paradigm is procedural or object-oriented.

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

4. For at least a couple of programming languages I've used, I remember hearing recommendations not to use recursion if it gets beyond a certain depth because its stack isn't that deep.

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

#12

Recursion is an expression directly or indirectly referencing itself.

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

Consider recursive acronyms as a simple example:

将递归首字母缩写作为一个简单的例子:

• GNU stands for GNU's Not Unix
• GNU代表GNU而不是Unix
• PHP stands for PHP: Hypertext Preprocessor
• PHP代表超文本预处理器。
• YAML stands for YAML Ain't Markup Language
• YAML表示YAML不是标记语言
• WINE stands for Wine Is Not an Emulator
• 葡萄酒代表的是葡萄酒不是模拟器
• VISA stands for Visa International Service Association
• VISA代表VISA国际服务协会

More examples on Wikipedia

在*上更多的例子

#13

Here's a simple example: how many elements in a set. (there are better ways to count things, but this is a nice simple recursive example.)

这里有一个简单的例子:一个集合中有多少个元素。

First, we need two rules:

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

1. if the set is empty, the count of items in the set is zero (duh!).
2. 如果集合为空，则集合中的项的计数为零(duh!)
3. if the set is not empty, the count is one plus the number of items in the set after one item is removed.
4. 如果该集合不是空的，则计数为1加上删除一个项目后集合中的项数。

Suppose you have a set like this: [x x x]. let's count how many items there are.

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

1. the set is [x x x] which is not empty, so we apply rule 2. the number of items is one plus the number of items in [x x] (i.e. we removed an item).
2. 集合是[x x x]它不是空的，所以我们应用规则2。项目的数量是1加上[x]中项目的数量(即我们删除了一个项目)。
3. the set is [x x], so we apply rule 2 again: one + number of items in [x].
4. 集合是[x]，因此我们再次应用规则2:在[x]中有一个+个数的项。
5. the set is [x], which still matches rule 2: one + number of items in [].
6. 集合是[x]，它仍然匹配规则2:1 +[]中的项数。
7. Now the set is [], which matches rule 1: the count is zero!
8. 现在集合是[]，它匹配规则1:计数为0 !
9. Now that we know the answer in step 4 (0), we can solve step 3 (1 + 0)
10. 既然我们知道了第4步(0)的答案，我们就可以解出第3步(1 + 0)
11. Likewise, now that we know the answer in step 3 (1), we can solve step 2 (1 + 1)
12. 同样，既然我们已经知道了步骤3(1)的答案，我们就可以解出步骤2 (1 + 1)
13. And finally now that we know the answer in step 2 (2), we can solve step 1 (1 + 2) and get the count of items in [x x x], which is 3. Hooray!
14. 最后，我们已经知道了步骤2(2)的答案，我们可以解出步骤1(1 + 2)得到[x x x]项的个数，也就是3。万岁!

We can represent this as:

我们可以把它表示为:

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

When applying a recursive solution, you usually have at least 2 rules:

当应用递归解决方案时，通常至少有两个规则:

• the basis, the simple case which states what happens when you have "used up" all of your data. This is usually some variation of "if you are out of data to process, your answer is X"
• 这是一个简单的例子，说明当你“用完”了所有的数据后会发生什么。这通常是"如果你没有数据处理，你的答案是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."
• 递归规则，它说明如果你仍然有数据会发生什么。这通常是一种规则，它说“做一些事情让你的数据变得更小，并将你的规则重新应用到较小的数据集中。”

If we translate the above to pseudocode, we get:

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

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

There's a lot more useful examples (traversing a tree, for example) which I'm sure other people will cover.

有很多有用的例子(例如，穿越一棵树)，我相信其他人会讲到。

#14

A recursive statement is one in which you define the process of what to do next as a combination of the inputs and what you have already done.

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

For example, take factorial:

例如,阶乘:

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

But it's easy to see factorial(6) also is:

但很容易看出阶乘(6)也是:

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

So generally:

所以一般:

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

Of course, the tricky thing about recursion is that if you want to define things in terms of what you have already done, there needs to be some place to start.

当然，递归的棘手之处在于，如果你想用你已经做过的事情来定义事物，就需要从某个地方开始。

In this example, we just make a special case by defining factorial(1) = 1.

在本例中，我们只是通过定义factorial(1) = 1来构造一个特例。

Now we see it from the bottom up:

现在我们从下往上看:

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

Since we defined factorial(1) = 1, we reach the "bottom".

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

Generally speaking, recursive procedures have two parts:

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

1) The recursive part, which defines some procedure in terms of new inputs combined with what you've "already done" via the same procedure. (i.e. factorial(n) = n*factorial(n-1))

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

2) A base part, which makes sure that the process doesn't repeat forever by giving it some place to start (i.e. factorial(1) = 1)

2)一个基本部分，通过给出起始位置(即factorial(1) = 1)来确保进程不会永远重复。

It can be a bit confusing to get your head around at first, but just look at a bunch of examples and it should all come together. If you want a much deeper understanding of the concept, study mathematical induction. Also, be aware that some languages optimize for recursive calls while others do not. It's pretty easy to make insanely slow recursive functions if you're not careful, but there are also techniques to make them performant in most cases.

一开始你可能会有点迷惑不解，但只要看一大堆例子，就会发现它们都是一致的。如果你想对这个概念有更深刻的理解，那就学习数学归纳法。另外，请注意，有些语言优化递归调用，而其他语言则不优化。如果不小心，很容易使递归函数极其缓慢，但是在大多数情况下，也有一些技术使它们具有性能。

Hope this helps...

希望这有助于……

#15

I like this definition:
In recursion, a routine solves a small part of a problem itself, divides the problem into smaller pieces, and then calls itself to solve each of the smaller pieces.

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

I also like Steve McConnells discussion of recursion in Code Complete where he criticises the examples used in Computer Science books on Recursion.

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

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.

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

I thought this was a very interesting point to raise and may be a reason why recursion is often misunderstood.

我认为这是一个非常有趣的问题，可能是递归经常被误解的原因之一。

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

编辑:这不是对Dav答案的挖掘——我在发布这篇文章时并没有看到这个回复

#16

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

1)。如果一个方法可以调用它自己，那么它就是递归的;直接:

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

or indirectly:

或间接地:

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

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

2.) When to use recursion

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.) People use recursion only when it is very complex to write iterative code. For example, tree traversal techniques like preorder, postorder can be made both iterative and recursive. But usually we use recursive because of its simplicity.

3)。只有当编写迭代代码非常复杂时，人们才会使用递归。例如，树遍历技术，如preorder、postorder都可以进行迭代和递归。但通常我们使用递归是因为它很简单。

#17

To recurse on a solved problem: do nothing, you're done.
To recurse on an open problem: do the next step, then recurse on the rest.

要递归解决的问题:什么都不做，就完成了。要递归打开的问题:执行下一步，然后递归其余的问题。

#18

Well, that's a pretty decent definition you have. And wikipedia has a good definition too. So I'll add another (probably worse) definition for you.

这是一个很好的定义。*也有一个很好的定义。因此我将为您添加另一个(可能更糟糕的)定义。

When people refer to "recursion", they're usually talking about a function they've written which calls itself repeatedly until it is done with its work. Recursion can be helpful when traversing hierarchies in data structures.

当人们提到“递归”时，他们通常指的是他们编写的一个函数，这个函数不断地调用自己，直到它完成工作。当在数据结构中遍历层次结构时，递归是有用的。

#19

An example: A recursive definition of a staircase is: A staircase consists of: - a single step and a staircase (recursion) - or only a single step (termination)

举个例子:楼梯的递归定义是:楼梯由:—单级和楼梯(递归)—或者仅仅是单级(终止)组成

#20

In plain English: Assume you can do 3 things:

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

1. Take one apple
2. 拿一个苹果
3. Write down tally marks
4. 写下数字标记
5. Count tally marks
6. 计数统计标志

You have a lot of apples in front of you on a table and you want to know how many apples there are.

桌上有很多苹果你想知道有多少苹果。

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

The process of repeating the same thing till you are done is called recursion.

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

I hope this is the "plain english" answer you are looking for!

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

#21

A recursive function is a function that contains a call to itself. A recursive struct is a struct that contains an instance of itself. You can combine the two as a recursive class. The key part of a recursive item is that it contains an instance/call of itself.

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

Consider two mirrors facing each other. We've seen the neat infinity effect they make. Each reflection is an instance of a mirror, which is contained within another instance of a mirror, etc. The mirror containing a reflection of itself is recursion.

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

A binary search tree is a good programming example of recursion. The structure is recursive with each Node containing 2 instances of a Node. Functions to work on a binary search tree are also recursive.

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

#22

This is an old question, but I want to add an answer from logistical point of view (i.e not from algorithm correctness point of view or performance point of view).

这是一个老问题，但我想从逻辑的角度(I)补充一个答案。e不是从算法正确性的角度或性能的角度)。

I use Java for work, and Java doesn't support nested function. As such, if I want to do recursion, I might have to define an external function (which exists only because my code bumps against Java's bureaucratic rule), or I might have to refactor the code altogether (which I really hate to do).

我使用Java工作，而Java不支持嵌套函数。因此，如果我想要进行递归，我可能需要定义一个外部函数(它的存在仅仅是因为我的代码与Java的官僚规则冲突)，或者我可能需要对代码进行重构(我真的不喜欢这样做)。

Thus, I often avoid recursion, and use stack operation instead, because recursion itself is essentially a stack operation.

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

#23

You want to use it anytime you have a tree structure. It is very useful in reading XML.

只要有树结构，就可以使用它。它在读取XML时非常有用。

#24

Recursion as it applies to programming is basically calling a function from inside its own definition (inside itself), with different parameters so as to accomplish a task.

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

#25

"If I have a hammer, make everything look like a nail."

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

Recursion is a problem-solving strategy for huge problems, where at every step just, "turn 2 small things into one bigger thing," each time with the same hammer.

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

Example

Suppose your desk is covered with a disorganized mess of 1024 papers. How do you make one neat, clean stack of papers from the mess, using recursion?

假设你的桌子上堆满了杂乱无章的1024份文件。如何使用递归将一堆乱七八糟的文件整理成一堆?

1. Divide: Spread all the sheets out, so you have just one sheet in each "stack".
2. 除:把所有的纸都摊开，所以你在每个“堆栈”里只有一张纸。
3. Conquer:
   2. Go around, putting each sheet on top of one other sheet. You now have stacks of 2.
   3. 到处走，把每一张纸放在另一张上面。你现在有2个堆栈。
   4. Go around, putting each 2-stack on top of another 2-stack. You now have stacks of 4.
   5. 转一圈，把每个2-stack放在另一个2-stack的上面。现在你有一堆4个。
   6. Go around, putting each 4-stack on top of another 4-stack. You now have stacks of 8.
   7. 转一圈，把每一个4-stack放在另一个4-stack的上面。现在有8个堆栈。
   8. ... on and on ...
   9. …等等……
   10. You now have one huge stack of 1024 sheets!
   11. 你现在有一大堆1024张!
4. 征服:到处走，把每一页放在另一页之上。现在你有一堆2。转一圈，把每个2-stack放在另一个2-stack的上面。现在你有一堆4个。转一圈，把每一个4-stack放在另一个4-stack的上面。你现在有8堆。等等……你现在有一大堆1024张!

Notice that this is pretty intuitive, aside from counting everything (which isn't strictly necessary). You might not go all the way down to 1-sheet stacks, in reality, but you could and it would still work. The important part is the hammer: With your arms, you can always put one stack on top of the other to make a bigger stack, and it doesn't matter (within reason) how big either stack is.

请注意，这是相当直观的，除了计算所有东西(这并不是严格必要的)。在现实中，你可能不会一直走到一页一页的书架，但你可以，而且它仍然可以工作。重要的是锤子:用你的手臂，你总是可以把一堆叠叠在另一堆上，形成一个更大的堆栈，而且(在合理的范围内)这两个堆栈有多大并不重要。

#26

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.

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

#27

hey, sorry if my opinion agrees with someone, I'm just trying to explain recursion in plain english.

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

suppose you have three managers - Jack, John and Morgan. Jack manages 2 programmers, John - 3, and Morgan - 5. you are going to give every manager 300$ and want to know what would it cost. The answer is obvious - but what if 2 of Morgan-s employees are also managers?

假设你有三个经理——杰克、约翰和摩根。杰克管理着两个程序员，约翰- 3和摩根- 5。你会给每个经理300美元，并想知道这要花多少钱。答案是显而易见的——但如果摩根的两名员工也是管理者呢?

HERE comes the recursion. you start from the top of the hierarchy. the summery cost is 0$. you start with Jack, Then check if he has any managers as employees. if you find any of them are, check if they have any managers as employees and so on. Add 300$ to the summery cost every time you find a manager. when you are finished with Jack, go to John, his employees and then to Morgan.

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

You'll never know, how much cycles will you go before getting an answer, though you know how many managers you have and how many Budget can you spend.

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

Recursion is a tree, with branches and leaves, called parents and children respectively. When you use a recursion algorithm, you more or less consciously are building a tree from the data.

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

#28

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

在简单的英语中，递归意味着一次又一次的重复。

In programming one example is of calling the function within itself .

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

Look on the following example of calculating factorial of a number:

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

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

#29

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

任何算法在数据类型上都表现出结构性递归，如果基本是由一个switch语句组成，每个数据类型都有一个case。

for example, when you are working on a type

例如，当您处理类型时

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

a structural recursive algorithm would have the form

结构递归算法应该有这种形式

 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

this is really the most obvious way to write any algorith that works on a data structure.

这是写任何在数据结构上工作的藻类的最明显的方式。

now, when you look at the integers (well, the natural numbers) as defined using the Peano axioms

现在，当你看用皮亚诺公理定义的整数(嗯，自然数)

 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.

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

#30

function call itself or use its own definition.

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