递归递归（recursion）是编程中的一个重要概念。很多编程语言，不仅限于函数式编程语言，都有递归这样的结构。从代码上来说，递归允许一个函数在其内部调用该函数自身。有些函数式编程语言并没有循环这样的结构，而是通过递归来实现循环。递归和循环在表达能力上是相同的，只不过命令式编程语言偏向于使用循环，而函数式编程语言偏向于使用递归。递归的优势在于天然适合于那些需要用分治法（divide and conquer）解决的问题，把一个大问题划分成小问题，以递归的方式解决。经典的通过递归解决的问题包括阶乘计算、计算最大公约数的欧几里德算法、汉诺塔、二分查找、树的深度优先遍历和快速排序等。
递归分为单递归和多递归。单递归只包含一个对自身的引用；而多递归则包含多个对自身的引用。单递归的例子包括列表遍历和计算阶乘等；多递归的例子包括树遍历等。在具体的编程实践中，单递归可以比较容易改写成使用循环的形式，而多递归则一般保持递归的形式。清单 12 给出了 JavaScript 实现的计算阶乘的递归写法。
清单 12. 递归方式计算阶乘1
2
3
4
5
6
7
| int fact(n) {
if (n === 0) {
return 1;
} else {
return n * fact(n - 1);
}
}
|
而下面的清单 13 则是 JavaScript 实现的使用循环的写法。
清单 13. 循环方式计算阶乘1
2
3
4
5
6
7
| int fact_i(n) {
let result = 1;
for (let i = n; i > 0; i--) {
result = result * i;
}
return result;
}
|
有一种特殊的递归方式叫尾递归。如果函数中的递归调用都是尾调用，则该函数是尾递归函数。尾递归的特性使得递归调用不需要额外的空间，执行起来也更快。不少编程语言会自动对尾递归进行优化。
下面我们以欧几里德算法来说明一下尾递归。该算法的 Java 实现比较简单，如清单 14 所示。函数 gcd 的尾调用是递归调用 gcd 本身。
清单 14. 尾递归的方式实现欧几里德算法1
2
3
4
5
6
| int gcd(x, y) {
if (y == 0) {
return x;
}
return gcd(y, x % y);
}
|
尾递归的特性在于实现时可以复用函数的当前调用栈的帧。当函数执行到尾调用时，只需要简单的 goto 语句跳转到函数开头并更新参数的值即可。相对于循环，递归的一个大的问题是层次过深的函数调用栈导致占用内存空间过大。对尾递归的优化，使得递归只需要使用与循环相似大小的内存空间。 |
