JavaScript递归详解：斐波那契实现、时间空间复杂度及调用栈分析

前言

在开发业务逻辑时，我们时常会碰到需要运用递归的场景，例如处理树形结构的遍历操作。

本文将以计算斐波那契数这一经典案例为切入点，深入剖析递归原理。我们将借助绘制递归树的方法，清晰展示递归的时间复杂度、空间复杂度以及具体的执行顺序，期待对各位开发者有所帮助。

递归的基本理解

表象理解

函数会自己调用自己
每一次调用，函数的参数都会收敛变小

实质理解

把一个大问题变成1个或n个小问题
用同样的逻辑来解决这些问题
最后把他拼凑起来，拼成全局问题

具体实现

先写Base case，定义基线条件，判断其是否为最小号问题，避免死循环
Recursive rule：递归规则

实例解析

接下来我们通过一个实例来讲解递归的应用。

求斐波那契数

求特定位置的斐波那契数，用递归实现代码很简单，接下来我们先看下斐波那契数的概念。

0号位置的斐波那契数是0
1号位置的斐波那契数是1
n(n>1)号位置的斐波那契数等于 n-1位置的斐波那契数 + n-2位置的斐波那契数

我们知道怎么计算斐波那契数后，就可以用递归来将其实现了。

我们可以将上述递归的理解中应用到求斐波那契数里，实现思路和实现代码如下：

Base case: 0号位置的斐波那契数是0，1号位置的斐波那契数是1。即:n === 0 return 0, n === 1 return 1;
Recursive rule: n号位置的值 = n - 1位置的值 + n - 2位置的值，即:fibonacciNumbers(n - 1) + fibonacciNumbers( n - 2);

const fibonacciNumbers = function(n){
    // base case
    if(n === 0){
        return 0;
    }else if(n === 1){
        return 1;
    }
    
    // Recursive rule
    return fibonacciNumbers(n - 1) + fibonacciNumbers( n - 2);
}

时间复杂度分析

我们将上述代码执行过程转换成如下图所示的递归树，观察二叉树中的节点后我们发现如下规律：

第0层有1个节点，第1层有2个节点，第2层有4个节点，第3层...第n层，每一层的节点数都是上一层的2倍。
即：1 + 2 + 4 + 8 + 2^(n-1)，等比数列求和后：2^n，时间复杂度为：O(2^n)。
最后一层结点的总数，远远超过其他所有层的总数。
时间复杂度取决于递归树中一共有多少节点。
所有递归的时间复杂度都可以通过递归树来分析。

空间复杂度分析

分析空间复杂度我们可以通过递归的执行顺序来分析，我们将上述代码的执行顺序整理成递归图标示其执行顺序，我们发现如下规律：

由于冯诺伊曼体系的影响，递归树执行时采用深度优先的方式执行。即：顺着一条线执行到底（蜜橙色线条）。
图中每一层执行时的bp全称为：break point，每一层执行到bp时，会将当前层的变量(n)记录一下，放进Call stack中。
由于执行递归树中的每一层时，都会有一个Call stack操作，将当前层的变量(n)放进去，因此递归树中有多少个调用栈取决于递归树的层数，因此空间复杂度为O(n)。
空间复杂度与节点总数关系不大，与其在Call stack里总共存了多少层直接相关。
所有递归的空间复杂度都可以通过递归树来分析。

执行顺序分析

上述递归图的执行顺序如下图所示，接下来带着代价来分析下每一步都做了哪些事情：

当函数执行到return fibonacciNumbers(n - 1) + fibonacciNumbers( n - 2) 的时候，由于冯诺伊曼体系的影响，它不会并行执行，他会先执行fibonacciNumbers(n - 1)函数，触发基线条件时，return到上一层，取出其在上一层在call Stack中存储的n的值，然后再去执行fibonacciNumbers( n - 2)函数，计算它右子树的值。
因此他会先执行fibonacciNumbers(n - 1)函数，即:F(4) => F(3) ... =>F1（图中的第1行）
当他执行到F(1)的时候，n = 1，触发基线条件return 1返回到上一层F(2)，即图中的第2行
返回到F(2)层时，取出当前层Call Stack中存储的n的值，执行fibonacciNumbers(n - 2)函数，执行到F(0)，即图中的第3行
此时F(0)中n的值为0，触发基线条件，return 0，即图中的第4行
此时(2)节点的左子树和右子树的值都计算出来了，因此可以执行fibonacciNumbers(n - 1) + fibonacciNumbers( n - 2)函数，将左、右子树的值相加，即得到了F(2)的值，然后return至上一层F(3)，即图中的第5行。
返回到F(3)时，与第3步一样，获取其右子树的值，然后重复第3至6步的步骤，直至计算出F(3)和F(2)的值，将其相加就得出了F(4)的值，此时F(4)处的值就是我们需要求的斐波那契数，即图中的第6～16行。

以上就是深入了解JavaScript中递归的理解与实现的详细内容，更多关于JavaScript递归的资料请关注本站其它相关文章！

深入解析JavaScript递归：原理、复杂度与执行流程

前言