递归的本质

一段程序由流程 + 数据构成。一个方法也是如此，只是方法就是将流程+数据打包，然后取个名字，提供传参，返回结果。

一个函数由函数签名和方法体两部分组成

String getName(String id) {
    String name = "Hory" + id;
    return name;
}
1
2
3
4

在上述的函数中，

• 函数签名为：String getName(String id)

• 方法体为String name = “Hory” + id; return name; 也就是花括号中的内容

而函数签名又通常包含三部分：

• 返回值
• 参数
• 方法名

对于一个迭代方法，很好理解，就是传入参数执行方法体然后返回结果就完事了。

从计算机层面来讲，执行一段代码，底层首先会创建一个栈，每当执行到一个函数时，会创建一个栈帧压入栈中，而这个栈帧中存放的东西就是这个函数相关的信息（函数名，参数等）

对于一个迭代的函数，很好理解，首先会创建一个栈帧，然后执行里面的代码，如果该函数内部又调用了另外一个函数（姑且称为子函数，相对应地称调用子函数的函数为母函数），则会再次为子函数也创建一个栈帧并压入栈中（如果子函数又调用了另外的函数，则依此类推），子函数执行完毕，将子函数栈帧抛出，接着执行母函数未执行完的代码（栈帧中存放着该函数的信息，其中就包含程序计数器，它就是用来记录该函数执行到哪一行）。

但是对于一个递归函数呢，就有点匪夷所思了。因为，该函数内部自己调用了自己！！

其实，递归的执行过程也是跟迭代没有任何区别，要说区别，应该是就是母函数在内部调用了自己，但是，真的是自己调用自己吗，答案是：不是！只是看起来是而已。

上面讲了，一个函数包含两部分：函数签名和方法体，当一个递归函数在内部调用自己的时候，其实底层会重新以该母函数为模板（说白了就是复制）创建一个新的函数，只不过这个新的函数跟母函数长得一样（函数签名和方法体，除了函数名不一样），就好比，一对双胞胎长得一模一样，但是名字不一样，他们也不是同一个人是一个道理。

所以，当一个递归函数在其内部调用“自己”的时候，整个过程其实是这样的，首先为最外层函数创建一个栈帧并压入栈中，然后执行代码，执行到调用自己的这个函数时，则以母函数为模板复制一个新的函数，并为此函数创建一个新的栈帧压入栈中，然后继续执行代码，以此类推，但是如果这样不是死循环了吗，因此，递归函数有个要求，就是一定要有终止条件，也就是通常所说的递归出口。

综上所述，递归函数看起来是自己调用了自己，其实不是，只不过创建重复函数的这个工作，计算机底层帮我们完成了。当然，你也可以自己编写n个这种除了名字其余部分（参数类型，返回值类型，方法体）一模一样的函数，然后依次调用，效果和递归是一样的。这也解释了，递归的代码通常比较简洁。

比如计算 1 加到 n 的结果

递归实现：

int plus(int n) {
    if (n == 0) return 0;
    return n + plus(n-1);
}
1
2
3
4

等价于迭代实现：

int plus(int n) {
    return n + plus_1(n-1);
}

int plus_1(int n) {
    return n + plus_2(n-1);
}

int plus_2(int n) {
    return n + plus_3(n-1);
}

...
1
2
3
4
5
6
7
8
9
10
11
12
13

至于需要创建多少个 plus 函数，这要取决于n为多少，随着创建的 plus 函数越来越多，传递到后面的 n 也越来越小，当 n 成为 0 时，即终止创建，总共大概需要创建 n 个plus函数。

而这个你手动创建 n 个 plus 函数的过程，等价于递归函数中的 if (n == 0) return 0; 这个就是递归函数的终止条件。

当你在递归函数中写下这一行时，计算机底层会判断，直到该条件成立才终止创建新的 plus 函数。

看完这篇文章，再看这篇文章是不是就很好理解了：《关于递归前后语句执行顺序》