一、递归的时间复杂度

递归算法的时间复杂度 = 递归次数 $\times$ 每次递归的时间复杂度。

递归次数：可以通过画递归树，数递归树的节点数，得到递归次数。

二、递归的空间复杂度

递归算法的空间复杂度 = 递归深度 $\times$ 每次入栈的空间复杂度 。

三、例子

3.1 斐波那契数列求和

视频教程推荐：【程序日常】采用栈的方式还原递归整个执行流程_哔哩哔哩

以计算斐波那契数列为例，代码如下：

int fib(int i) { // 计算斐波那契数列的第 i 项if (i <= 0) return 0;if (i == 1) return 1;return fib(i - 1) + fib(i - 2);
}

假设计算的是 fib(4)，计算过程过程如下：

fib(4) 入栈，执行到第四行 return fib(3) + fib(2)，按照从左往右计算，先算 fib(3)；
fib(3) 入栈。执行到第四行 return fib(2) + fib(1)，按照从左往右计算，先算 fib(2)；
fib(2) 入栈。执行到第四行 return fib(1) + fib(0)，按照从左往右计算，先算 fib(1)；
fib(1) 入栈。执行到第三行 if (i == 1) return 1，返回 1；
fib(1) 出栈。返回的 1 交给 fib(2)，fib(2) 继续执行第四行 return 1 + fib(0)；
fib(0) 入栈。执行到第二行 if (i <= 0) return 0 ，返回 0；
fib(0) 出栈。返回的 0 交给 fib(2)，fib(2) 继续执行第四行 return 1 + 0，返回 1；
fib(2) 出栈。返回的 1 交给 fib(3)，fib(3) 继续执行第四行 return 1 + fib(1)；
fib(1) 入栈。执行到第三行 if (i == 1) return 1，返回 1；
fib(1) 出栈。返回的 1 交给 fib(3)，fib(3) 继续执行第四行 return 1 + 1，返回 2；
fib(3) 出栈。返回的 2 交给 fib(4)，fib(4) 继续执行第四行 return 2 + fib(2);
fib(2) 入栈。执行到第四行 return fib(1) + fib(0)，按照从左往右计算，先算 fib(1)；
fib(1) 入栈。执行到第三行 if (i == 1) return 1，返回 1；
fib(1) 出栈。返回的 1 交给 fib(2)，fib(2) 继续执行第四行 return 1 + fib(0)；
fib(0) 入栈。执行到第二行 if (i <= 0) return 0 ，返回 0；
fib(0) 出栈。返回的 0 交给 fib(2)，fib(2) 继续执行第四行 return 1 + 0，返回 1；
fib(2) 出栈。返回的 1 交给 fib(4)，fib(4) 继续执行第四行 return 2 + 1，返回 3，程序结束。

3.2 递归次数和递归深度

从 3.1 的例子可以看出，递归次数影响时间复杂度，递归深度影响空间复杂度。时间复杂度比较好理解。此处不解释。

请添加图片描述

图 1

空间复杂度涉及到递归栈，结合图1，我们可以分析出以下三点：

整个计算过程是线性进行的：比如 fib(3) + fib(2)，这时并不会同时把 fib(3) 和 fib(2)入栈，而是按顺序从左往右，把 fib(3) 入栈，执行 fib(3)。
递归深度影响空间复杂度：最深的一次递归所占用的空间（这里的空间包含之前递归所入栈的空间），就是整个计算过程中所能占用的最大空间了。整个过程是线性的，其中不断有出栈和入栈，占用的空间始终不会超过，最深的那次递归时，所用的空间。
这个例子里的空间复杂度，就是 fib(4)入栈 + fib(3)入栈 + fib(2)入栈 + fib(1)入栈 所占用的空间（或者 fib(4)入栈 + fib(3)入栈 + fib(2)入栈 + fib(0)入栈所占用的空间，在本例中他们是一样的）。