Question

如果我们需要重复地多次计算相同的问题，通常可以选择用递归或者循环两种不同的方法。递归是在一个函数的内部调用这个函数自身。而循环则是通过设置计算的初始值及终止条件，在一个范围内重复运算。比如求1＋2＋…＋n，我们可以用递归或者循环两种方式求出结果。对应的代码如下：

通常递归的代码会比较简洁。在上面的例子里，递归的代码只有一个语句，而循环则需要4个语句。在树的前序、中序、后序遍历算法的代码中，递归的实现明显要比循环简单得多。在面试的时候，如果面试官没有特别的要求，应聘者可以尽量多采用递归。

面试小提示：

通常基于递归实现的代码比基于循环实现的代码要简洁很多，更加容易实现。如果面试官没有特殊要求，应聘者可以优先采用递归的方法编程。

递归虽然有简洁的优点，但它同时也有显著的缺点。递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间。这就不难理解上述的例子中递归实现的效率不如循环。

另外，递归中有可能很多计算都是重复的，从而对性能带来很大的负面影响。递归的本质是把一个问题分解成两个或者多个小问题。如果多个小问题存在相互重叠的部分，那么就存在重复的计算。在面试题9斐波那契数列及面试题43n个骰子的点数中我们将详细地分析递归和循环的性能区别。

除了效率之外，递归还有可能引起更严重的问题：调用栈溢出。前面分析中提到需要为每一次函数调用在内存栈中分配空间，而每个进程的栈的容量是有限的。当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。在上述例子中，如果输入的参数比较小，如10，它们都能返回结果55。但如果输入的参数很大，如5000，那么递归代码在运行的时候就会出错，但运行循环的代码能得到正确的结果12502500。