递归是一种很常见的算法,许多循环算法可以转变成递归。递归的一般形式是这样的:
function fn(n){
if(n === 1){
return 2; // 1
}
return fn(n - 1) + n; // 2
}
也就是递归一般会有一个判断,这是递归算法的出口(1 处);还有一个返回这个函数的执行结果(2 处);这两点是实现递归的关键。如果没有出口,递归就会变成死循环,而如果没有函数自身内部调用就无法构成递归。
很多人刚开始学递归的时候估计都有这么一种感觉(我就是),看到这样的表达式:fn(n - 1) + n
,有点懵逼,一个函数怎么能在它自己内部再调用自己呢?思考了之后大概明白了一些(难以言表),确实可以在内部调用,最后可能脑袋里会有一个类似“洋葱”的结构,函数包裹者函数,上面那种递归是最简单的一种形式了,差不多能想明白。
要理解递归需要先了解递归的运行机制。许多递归算法可以由循环来实现,但是用递归有时会更简洁一些。举个例子,一个非常简单的算法:输入一个正整数,计算出从一到这个数的和,如果使用循环可以这么写:
function sum(n){
var s = 0;
while(n){
s += n;
n --;
}
return s;
}
而如果使用递归呢?就变成了这样:
function sum(n){
if(n === 1){
return 1;
}
return n + sum(n - 1);
}
很明显后者比前者代码量小。想要把递归写出来就需要考虑递归的出口,在这里出口是 1,因为第一个数总是 1。假如 n = 6,下面是整个函数大概的运行的过程:
sum(6);
6 + sum(5);
6 + 5 + sum(4);
6 + 5 + 4 + sum(3);
6 + 5 + 4 + 3 + sum(2);
6 + 5 + 4 + 3 + 2 + sum(1);
当 n === 1 时,return 1;
6 + 5 + 4 + 3 + 2 + 1; // 21
上面的运行过程可能会有疑惑,既然函数被 return 出去了(return n + sum(n - 1);
),为什么能会继续计算呢?
因为虽然有 return
语句但是返回的是函数执行,还要执行返回的这个函数,因此最外层的 sum 函数并没有执行完,他需要等待里面的函数执行完才算执行完,而里面的函数又会 return 出更里面的函数执行,就这样一层层执行,外层函数总是等待着内层函数执行完毕。于是就变成了这个样子(假设 n 为 4):
sum(4)
从图中可以看出,要想获得 sum(4)
的值就需要先获得 sum(3)
的值,想要获得 sum(3)
的值就要获得 sum(2)
的值,以此类推直至得到 sum(1)
的值,这个过程被称为 递推;而知道了 sum(1)
的值之后,sum(2)
的值也就知道了,以此类推,sum(4)
的值也就求得了,这个过程被称为 回溯。
因此,递归包括递推
和回溯
两部分。递推
时将函数压入栈中,而回溯
是将栈里的元素弹出。一个函数在执行时,会把这个函数送进执行栈中,当函数执行完毕后,会把该函数从栈内移出。
execute-stack
因为栈是“先进后出”,因此 sum(4)
最先入栈,但最后才出来。
执行栈中的函数们并不是“线式”的,而是嵌套式的,比如下面的函数:
function a(){
b();
c();
d();
}
function b(){
e();
}
function e(){
f();
}
a();
c();
当函数 a
执行时,入栈(只有函数执行时才会入栈)元素是这样的:
f
e
b
a
执行函数 a,入栈,a 中有函数 b 要执行,将 b 压入 a 函数的栈里(因为在 a 函数内部执行),b 函数里面有函数 e 执行,将 e 压入栈中,e 里面又有 f 执行,因此也将 f 压入栈中,当“b、e、f” 这些函数执行完毕后(应该说是 b 函数执行完,出栈),继续执行 a 函数下面的语句,执行 c 函数,将 c 函数入栈,执行 c 函数,函数执行完毕后,继续执行 d 函数,d 函数执行完毕后,a 函数也就执行完毕了,于是将 a 函数出栈。然后执行 a 函数后面的语句,将 c 函数入栈......
递归在算法中应用十分广泛,相较于循环迭代,递归显得更加优雅直观,代码易读性好一些。但是使用递归并不一定比迭代运行速度快,递归需要先递推后回溯,而迭代没有那么多的过程。
通过上面简单的例子可以看出,使用递归可以让我们使用更少的代码解决问题。
斐波那契数列问题通常用递归解决。输入一个数 n,返回斐波那契数列的第 n 项的值。
function fb(n){
return n > 0 ? (n <= 2 ? 1 : fb(n - 1) + fb(n - 2)) : 0;
}
fb(n - 1) + fb(n - 2)
。爬楼梯是一个经典的动态规划问题,而且基本上所有的动态规划问题都能用递归来解决。问题是这样的:上楼梯有两种上法,一种一次上一个台阶,另一种是一次上两个台阶。如果一个楼梯有 n 个台阶,试问有多少种上楼梯的步骤?假如一个楼梯只有三个台阶,那么就有三种上法:
而如果是 n 个台阶时,想一下最后一个台阶是如何上去的?显然,要么是从第 n-1 个台阶上去的,要么是从第 n-2 个台阶上去的,有两种上法。而爬楼梯的出口是只有一个台阶或者只有两个台阶时,分别是 1 种上法和两种上法,而别的台阶数则是递归的从 n-1 或者 n-2 个台阶开始上的上法:
function climbTheStairs(n){
return (n === 1 || n === 2) ? n : climbTheStairs(n - 1) + climbTheStairs(n - 2);
}
除了使用递归之外,递推也是可以实现的:
function climbTheStairs(n){
let arr = [];
arr[1] = 1;
arr[2] = 2;
for(let i = 3;i <= n;i ++){
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
输入一个 N 维数组,将这个数组变成一维数组。具体算法如下:
function flat(array) {
var result = [];
array.forEach(item => {
if(Array.isArray(item)){
var res = flat(item);
result = result.concat(res);
}else{
result.push(item);
}
});
return result;
}
这个例子中,多维数组是入口,而出口也是数组,不过是一维形式的,一维形式表明遍历的数组中的元素是基本数据类型,而非数组。首先我们需要先遍历数组,如果其中的元素类型还是数组,就需要再次调用自身,将该元素扁平化,把扁平化后的数组与我们要返回的数组拼接成一个数组。而这个元素类型不是数组时我们就直接 push 到数组当中,最后返回。
或者使用 ES6 当中的 reduce 函数来实现:
function flat(array) {
return array.reduce((prev,current) => {
return prev.concat(
!Array.isArray(current) ? current : flat(current)
);
},[]);
}
reduce 函数更加直观,初始累加器(prev)是空数组,current 是指当前遍历的数组中的元素,当当前的元素是数组时就再次调用 flat 函数,然后将 prev 与扁平化后的结果组合成一个数组,然后返回,返回的是一个数组,这个数组会又赋给 prev 变量。
假如有这么一个对象:
const obj = {
a: 1,
b: [1,2,3],
c: {},
d: {
e: 4,
f: {
g: 6
}
}
}
如何克隆出一个与这个对象一样的对象,而且两个对象之间没有什么关联。这里不考虑循环引用,只考虑只有数组和对象两种引用类型的情况。
首先,需要考虑传入的参数是对象、是数组还是其他的类型,如果是其他的类型就直接返回,而如果是数组,我们就要建立一个空数组,它是克隆后的结果,而如果是对象,就建立一个对象,它是克隆后的对象。然后遍历数组或者对象。这个递归函数的出口是非对象非数组类型的数据。代码如下:
function deepClone(object) {
var result;
if (Array.isArray(object)) {
// 是数组时
result = [];
object.forEach(item => {
// 把克隆的结果 push 进数组中
result.push(deepClone(item));
});
} else if (Object.prototype.toString.call(object) === "[object Object]") {
// 是对象时
result = {};
for (let key in object) {
// 把克隆的结果赋给 result 对象的属性
result[key] = deepClone(object[key]);
}
} else {
// 别忘了这个,不然没有出口
result = object;
}
// 返回最终结果
return result;
}
上面介绍了执行栈的概念,试想一个问题,如果递归太深,执行栈会不会满甚至溢出?比如斐波那契数列,当调用 fb(10)
时运行速度还是可以的,而运行 fb(100)
时可能就没有反映了。而如果使用循环,运行速度就会很快:
function fb(n){
if(n <= 2) return 1;
var first = 1;
var second = 1;temp;
for(let i = 3;i <= n;i ++){
temp = first;
first = second;
second = first + temp;
}
return second;
}
显然,使用循环代码不太好理解。另一种办法是使用爬楼梯当中使用数组方式来解决问题。
function fb(n){
if(n <= 2) return 1;
var arr = [0,1,1];
for(let i = 3;i <= n;i ++){
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
这种方法运行速度也比递归快得多,不好的一点是当 n 很大时比较占内存。
还有一种办法是使用缓存。试想一下,如果执行 fb(6)
,执行过程会是怎样的?如下:
fb(6) = fb(5) + fb(4);
fb(5) = fb(4) + fb(3);
fb(4) = fb(3) + fb(2);
fb(3) = fb(2) + fb(1);
fb(3) = fb(2) + fb(1);
fb(4) = fb(3) + fb(2);
fb(3) = fb(2) + fb(1);
fb(6) 调用时,会执行 fb(5) + fb(4),而 fb(5) 和 fb(4) 执行时都会执行 fb(3)
,fb(3) 执行时又会多次执行 fb(2)
和 fb(1)
,这也是递归慢的原因。如果我们不想让函数重复执行,可以设置一个对象或者函数把中间执行的结果存起来,然后取数组或者对象中的结果就行了,比如下面的代码:
function fb(n) {
let cache = [0, 1, 1];
function _fb(n) {
if (cache[n]) return cache[n];
cache[n] = _fb(n - 1) + _fb(n - 2);
return cache[n];
}
return _fb(n);
}
在函数内声明一个数组,用来缓存结果,然后内部重新写一个递归函数,调用时首先判断缓存数组中有没有数据,有的话就直接返回,没有就存值,最后返回结果。因此使用这种方式也能提高运行速度。
尾递归,从字面意思上看,大概就是递归是在函数最后调用的。但尾递归比较特殊,它确实是在函数尾部调用的,但在尾部调用的是函数自身。在一般的递归函数中,是首先执行递归调用,然后获取递归调用的返回值并计算结果;而尾递归首先执行计算,然后执行递归调用,将当前步骤的结果传递给下一个递归步骤,尾递归也是为了优化递归算法。比如计算一个数的阶乘,可以这么写:
function factorial(n){
return n <= 1 ? 1 : n * factorial(n - 1);
}
虽然这个函数是在尾部调用的,但它不是尾递归。上面已经说了,尾递归首先会执行计算,然后执行调用。而这个函数执行的步骤大致是这样的(假如 n == 6):
6 * f(5);
6 * (5 * f(4));
6 * (5 * (4 * f(3)));
6 * (5 * (4 * (3 * f(2))));
6 * (5 * (4 * (3 * (2 * f(1)))));
它是先递归调用,当回溯时才执行计算。而如果使用尾递归,则写法是这样的:
function factorial(n, r) {
return n <= 1 ? r * 1 : ft(n - 1, r * n);
}
当调用 factorial(6)
时,运算步骤大致如下:
factorial(6, 1)
factorial(5, 6);
factorial(4, 30);
factorial(3, 120);
factorial(2, 360);
factorial(1, 720);
当 n == 1,时就会返回 r*1,就得到了结果:720。可以发现,尾递归会先执行运算,然后执行调用,第二个参数 r
相当于缓存,它做计算,而第一个参数 n,更像是循环中的循环次数,每次减一。
下面是斐波那契数列的尾递归版本:
function fb(n, a = 1, b = 1){
return n <= 2 ? b : fb(n - 1, b, a + b);
}
调用过程:
fb(6, 1, 1)
fb(5, 1, 2);
fb(4, 2, 3);
fb(3, 3, 5);
fb(2, 5, 8);
对于深度克隆这种比较复杂的函数,如果使用尾递归是很难实现的,而使用尾递归的程序一般使用循环也可以解决问题。