递归的理解与实现

❝

知其然知其所以然

前言

我们在写业务代码的时候，或多或少都会遇到需要使用递归的场景，比如在遍历树形结构时。

本文将通过递归的经典案例：求斐波那契数来讲解递归，通过画递归树的方式来讲解其时间复杂度和空间复杂度以及递归的执行顺序，欢迎各位感兴趣的开发者阅读本文。

递归的基本理解

• 表象理解
  

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

• 实质理解
  

• 把一个大问题变成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);
}

时间复杂度分析

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

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

空间复杂度分析

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

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

执行顺序分析

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

• 当函数执行到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行。