JS复习 -- 递归

红太狼 2022-06-06 06:14 327阅读 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了嘛～