王甲评 2019-06-28
原文地址
递归概念很简单,“自己调用自己”(下面以函数为例)。
在分析递归之前,需要了解下 JavaScript 中“压栈”(call stack
) 概念。
栈是什么?可以理解是在内存中某一块区域,这个区域比喻成一个箱子,你往箱子里放些东西,这动作就是压栈。所以最先放下去的东西在箱子最底下,最后放下去的在箱子最上面。把东西从箱子中拿出来可以理解为*出栈。
所以得出结论,我们有个习惯,拿东西是从上面往下拿,最先放下去的东西在箱子的最底下,最后才能拿到。
在 JavaScript 中,调用函数时,都会发生压栈行为,遇到含 return
关键字的句子或执行结束后,才会发生出栈(pop)。
来看个例子,这个段代码执行顺序是怎样的?
function fn1() { 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()
上面发生了一系列压栈出栈的行为:
fn
执行,fn
先压栈,放在栈(箱子)最底下fn1
,fn1
压栈在 fn
上面fn1
执行,遇到 return
关键字,返回 this is fn1
,fn1
出栈,箱子里现在只剩下 fn
fn
内部,fn1
执行完后,函数 fn2
开始执行,fn2
压栈,但是在 fn2
内部,遇到 fn3
,开始执行 fn3
,所以 fn3
压栈fn3
<= fn2
<= fn
,fn
在最底下fn3
内部遇到 return
关键字的句子,fn3
执行完结束后出栈,回到函数 fn2
中 ,fn2
也是遇到 return
关键字,继续出栈。fn
了,回到函数 fn
中,执行 console.log('All fn are done'
) 语句后,fn
出栈。上面步骤容易把人绕晕,下面是流程图:
再看下在 chrome 浏览器环境下执行:
先看下简单的 JavaScript 递归
function sumRange(num) { if (num === 1) return 1; return num + sumRange(num - 1) } sumRange(3) // 6
上面代码执行顺序:
sumRange(3)
执行,sumRange(3)
压栈,遇到 return
关键字,但这里还马上不能出栈,因为调用了 sumRange(num - 1)
即 sumRange(2)
sumRange(2)
压栈,以此类推,sumRange(1)
压栈,sumRange(1)
出栈返回 1,sumRange(2)
出栈,返回 2,sumRange(3)
出栈3 + 2 + 1
结果为 6看流程图
所以,递归也是个压栈出栈的过程。
递归可以用非递归表示,下面是上面递归例子等价执行
// for 循环 function multiple(num) { let total = 1; for (let i = num; i > 1; i--) { total *= i } return total } multiple(3)
如果上面例子修改一下,如下:
function multiple(num) { if (num === 1) console.log(1) return num * multiple(num - 1) } multiple(3) // Error: Maximum call stack size exceeded
上面代码第一行没有 return
关键字句子,因为递归没有终止条件,所以会一直压栈,造成内存泄漏。
递归容易出错点
好了,以上就是 JavaScript 方式递归的概念。
下面是练习题。
true
,如果不等,返回 false
。function reverse(str) { if(str.length <= 1) return str; return reverse(str.slice(1)) + str[0]; } reverse('abc')
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)
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])
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}})
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)
递归精髓是,往往要先想好常规部分是怎样的,在考虑递归部分,下面是 JavaScript 递归常用到的方法
slice
, concat
slice
, substr
, substring
Object.assign