用 JavaScript 的方式理解递归

栈是什么？可以理解是在内存中某一块区域，这个区域比喻成一个箱子，你往箱子里放些东西，这动作就是 压栈 。所以最先放下去的东西在箱子最底下，最后放下去的在箱子最上面。把东西从箱子中拿出来可以理解为**出栈*。

所以得出结论，我们有个习惯，拿东西是从上面往下拿，最先放下去的东西在箱子的最底下，最后才能拿到。

在 JavaScript 中，调用函数时，都会发生压栈行为，遇到含 return 关键字的句子或执行结束后，才会发生出栈（pop）。

来看个例子，这个段代码执行顺序是怎样的？

function `() {
    return 'this is fn1'
}

function fn2() {
    fn3()
    return 'this is fn2'
}

function fn3() {
    let arr = ['apple', 'banana', 'orange']
    return arr.length
}

function fn() {
    fn1()
    fn2()
    console.log('All fn are done')
}

fn()
复制代码

上面发生了一系列压栈出栈的行为：

1. 首先，一开始栈（箱子）是空的
2. 函数 fn 执行， fn 先压栈，放在栈（箱子）最底下
3. 在函数 fn 内部，先执行函数 fn1 ， fn1 压栈在 fn 上面
4. 函数 fn1 执行，遇到 return 关键字，返回 this is fn1 ， fn1 出栈，箱子里现在只剩下 fn
5. 回到 fn 内部， fn1 执行完后，函数 fn2 开始执行， fn2 压栈，但是在 fn2 内部，遇到 fn3 ，开始执行 fn3 ，所以 fn3 压栈
6. 此时栈中从下往上顺序为： fn3 <= fn2 <= fn ， fn 在最底下
7. 以此类推，函数 fn3 内部遇到 return 关键字的句子， fn3 执行完结束后出栈，回到函数 fn2 中 ， fn2 也是遇到 return 关键字，继续出栈。
8. 现在栈中只有 fn 了，回到函数 fn 中，执行 console.log('All fn are done' ) 语句后， fn 出栈。
9. 现在栈中又为空了。

上面步骤容易把人绕晕，下面是流程图：

再看下在 chrome 浏览器环境下执行：

3. 递归

先看下简单的 JavaScript 递归

function sumRange(num) {
  if (num === 1) return 1;
  return num + sumRange(num - 1)
}

sumRange(3) // 6
复制代码

上面代码执行顺序：

1. 函数 sumRange(3) 执行， sumRange(3) 压栈，遇到 return 关键字，但这里还马上不能出栈，因为调用了 sumRange(num - 1) 即 sumRange(2)
2. 所以， sumRange(2) 压栈,以此类推， sumRange(1) 压栈，
3. 最后， sumRange(1) 出栈返回 1， sumRange(2) 出栈，返回 2， sumRange(3) 出栈
4. 所以 3 + 2 + 1 结果为 6

看流程图

所以，递归也是个压栈出栈的过程。

递归可以用非递归表示，下面是上面递归例子等价执行

// for 循环
function multiple(num) {
    let total = 1;
    for (let i = num; i > 1; i--) {
        total *= i
    }
    return total
}
multiple(3)
复制代码

4. 递归注意点

如果上面例子修改一下，如下：

function multiple(num) {
    if (num === 1) console.log(1)
    return num * multiple(num - 1)
}

multiple(3) // Error: Maximum call stack size exceeded
复制代码

上面代码第一行没有 return 关键字句子，因为递归没有终止条件，所以会一直压栈，造成内存泄漏。

递归容易出错点

1. 没有设置终止点
2. 除了递归，其他部分的代码
3. 什么时候递归合适

好了，以上就是 JavaScript 方式递归的概念。

下面是练习题。

6. 练习题目

1. 写一个函数，接受一串字符串，返回一个字符串，这个字符串是将原来字符串倒过来。
2. 写一个函数，接受一串字符串，同时从前后开始拿一位字符对比，如果两个相等，返回 true ，如果不等，返回 false 。
3. 编写一个函数，接受一个数组，返回扁平化新数组。
4. 编写一个函数，接受一个对象，这个对象值是偶数，则让它们相加，返回这个总值。
5. 编写一个函数，接受一个对象，返回一个数组，这个数组包括对象里所有的值是字符串

7. 参考答案

参考1

function reverse(str) {
   if(str.length <= 1) return str; 
   return reverse(str.slice(1)) + str[0];
}

reverse('abc')
复制代码

参考2

function isPalindrome(str){ 
    if(str.length === 1) return true;
    if(str.length === 2) return str[0] === str[1]; 
    if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1)) 
    return false; 
}

var str = 'abba'
isPalindrome(str)
复制代码

参考3

function flatten (oldArr) {
   var newArr = [] 
   for(var i = 0; i < oldArr.length; i++){ 
    if(Array.isArray(oldArr[i])){ 
        newArr = newArr.concat(flatten(oldArr[i])) 
    } else { 
        newArr.push(oldArr[i])
     }
   }
   return newArr;
}

flatten([1,[2,[3,4]],5])
复制代码

参考4

function nestedEvenSum(obj, sum=0) {
    for (var key in obj) { 
        if (typeof obj[key] === 'object'){ 
            sum += nestedEvenSum(obj[key]); 
        } else if (typeof obj[key] === 'number' && obj[key] % 2 === 0){ 
            sum += obj[key]; 
        }
     } 
    
     return sum;
}

nestedEvenSum({c: 4,d: {a: 2, b:3}})
复制代码

参考5

function collectStrings(obj) {
    let newArr = []
    for (let key in obj) {
        if (typeof obj[key] === 'string') {
            newArr.push(obj[key])
        } else if(typeof obj[key] === 'object' && !Array.isArray(obj[key])) {
           newArr = newArr.concat(collectStrings(obj[key]))
        }
    }
    return newArr
}

var obj = {
        a: '1',
        b: {
            c: 2,
            d: 'dd'
        }
    }

collectStrings(obj)
复制代码

5. 总结

递归精髓是，往往要先想好常规部分是怎样的，在考虑递归部分，下面是 JavaScript 递归常用到的方法

• 数组： slice , concat
• 字符串: slice , substr , substring
• 对象： Object.assign