JS复习 -- 递归 红太狼 2022-06-06 06:14 152阅读 0赞 两个很常见的递归函数: // 阶乘 function factorial(n) { if (n == 1) return n; return n * factorial(n - 1) } console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120 // 斐波那契数列 function fibonacci(n){ return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2); } console.log(fibonacci(5)) // 1 1 2 3 5 递归的特点其实就是: 第一,将原始问题拆分,并且拆分得到的子问题和原始问题实现相同的功能。 第二,必须有一个出口让递归函数结束,否则递归将要无限执行。 递归函数存在一个问题: 当JS执行一个函数的时候,就会创建一个执行上下文。然后,这个执行上下文就会被压入执行上下文栈。如果递归不停的调用自身,那么执行上下文栈也就会越来越大。酱紫不太好对吧。 ## 尾调用 ## 这就是解决方案。 尾调用是什么: 指的就是,这个函数的最后一步是执行一个函数,并且,该被执行的函数的返回值就是本函数的返回值。 // 尾调用 function f(x){ return g(x); // 最后一个动作是执行g函数 } // 非尾调用 function f(x){ return g(x) + 1; // 执行g函数后又执行了一步加法 } 那么第一个尾调用的执行上下文变化: // 伪代码 ECStack.push(<f> functionContext); ECStack.pop(); ECStack.push(<g> functionContext); ECStack.pop(); 我们来解释一下,为什么会这样: 因为函数的调用栈还有执行上下文是为了保存函数内部状态的,尾调用由于是函数的最后一步操作,所以不需要保留外层函数的调用记录,因为调用位置、内部变量等信息都不会再用到了,只要直接用内层函数的调用记录,取代外层函数的调用记录就可以了。 但是,如果函数 g 中用到了f函数中的变量,形成闭包,f 就不会被弹出。 第二个则是: ECStack.push(<f> functionContext); ECStack.push(<g> functionContext); ECStack.pop(); ECStack.pop(); 我们可以看到使用了尾调用的递归函数,在上下文栈中只有一个函数入栈。简直厉害! **函数调用自身,称为递归。如果尾调用自身,就称为尾递归。** ## 优化 ## 下面,我们就来优化刚才的阶乘函数。 function factorial(n, res) { if (n == 1) return res; return factorial(n - 1, n * res) } console.log(factorial(4, 1)) // 24 多了一个参数,不过我们的上下文栈保持了干净。 新技能get了嘛~
还没有评论,来说两句吧...