由 发布
2013 年 6 月 21 日 (最后更新：2013 年 6 月 25 日)

递归

评分：3.9/5 (2744 票)
*****

递归


什么是递归？简单来说，就是函数调用自身。但它是如何发生的？为什么会发生，它的用途又是什么？

当我们谈论递归时，我们实际上是在谈论创建循环。让我们从一个基本的循环开始。

1
2
3
 
for(int i=0;  i<10; i++) {
     cout << "The number is: " << i << endl;
}


对于还不知道的人来说，这个基本循环会显示句子“The number is: ”，后面跟着“i”的值。就像这样。

The number is: 0
The number is: 1
The number is: 2
The number is: 3
The number is: 4
The number is: 5
The number is: 6
The number is: 7
The number is: 8
The number is: 9

在“for 循环”声明内部，我们有整型变量“i”，并将其初始值设置为 0。因此，第一次显示句子时，它显示“The number is: 0”。“for 循环”声明中“i++”的部分告诉程序，每次循环重复时，“i”的值都会增加 1。所以，下次显示句子时，它显示“The number is: 1”。
这个周期会一直重复，只要“i”的值小于 10。最后显示的句子将是“The number is: 9”。正如你所见，基本的“for 循环”声明有三个部分：一个初始值，继续重复必须保持的条件，以及一个修改表达式。包含在 {} 中的是程序执行的操作。Cout 是 console out（控制台输出）的缩写，用于将单词或字符打印到屏幕上。
那么这与递归有什么关系呢？记住，递归就是循环。如果我不想仅仅在屏幕上打印一条消息怎么办？循环还可以用于执行其他任务。

下面的代码是与上面相同的循环，只是现在它被用来调用一个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
using namespace std;

void numberFunction(int i) {
  cout << "The number is: " << i << endl;
}

int main() {

for(int i=0; i<10; i++) {
  numberFunction(i);
}

return 0;
}


我声明了一个 void 函数，这意味着它不返回任何值，并且接受一个 int i 参数。该函数名为 numberFunction，如你所见，它所做的只是显示句子“The number is: ”，后面跟着“i”的当前值。“for 循环”调用该函数，只要“i”的值小于 10，就会不断地调用该函数。

现在，通过递归，我们就不需要使用“for 循环”了，因为我们将进行设置，使我们的函数调用自身。让我们再重做一遍相同的程序，只是这次我们将在没有“for 循环”的情况下进行。我们将使用递归循环，就像这样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
using namespace std;

void numberFunction(int i) {
  cout << "The number is: " << i << endl;
  i++;
  if(i<10) {
    numberFunction(i);
  }
}

int main() {

int i = 0;
numberFunction(i);

return 0;
}


我们做到了！我们使用了递归！你可以看到 numberFunction 的调用只在程序的 main 部分进行了一次，但它从函数内部不断地被一次又一次地调用，只要 i 小于 10。