递归算法时间与空间复杂度分析

递归是一种强大的技术，可以解决很多复杂的问题。很多算法都建立递归之上，像树的遍历，深搜，广搜，还有很多强大的排序算法等。现在来分析以下这些常见的递归算法的时间复杂度是怎样的。

递归的时间复杂度=递归的深度*每层递归的代价

递归的空间复杂度=递归的深度*每次递归所需空间

求阶乘

int fac(int n){
    if(n<=1) return 1;
    return n*fac(n-1); 
}

时间复杂度

算法运算时间的递归式为：T(n) = T(n-1) + O(1)

总共递归n层，每层的时间复杂度为 O(1)，所以总的时间复杂度为 O(n*1) = O(n)

空间复杂度

总共递归 n 层，函数的每次调用产生的空间复杂度为 O(1)，所以总的空间复杂度为 O(n*1) = O(n)

注意

由于 int 大小的限制，它最多能求解16的阶乘，因为 int 最大值为2147483647，大于 2147483647 ,int 型变量就会变成负值。

求解斐波那契数列

斐波那契数列: 0 1 1 2 3 5 8 13

从 n 大于等于 2 开始，每个斐波那契数都是前两个数之和。

求解第 n 个斐波那契数是一个经典的问题，现在用递归来解决这个问题。

int fib(int n){
    if(n<=1) return n;
    return fib(n-1)+fib(n-2);
}

时间复杂度分析

算法运行时间的递归式为：T(n) = T(n-1) + T(n-2) + O(1)。

递归树是递归分析的常用工具，通过递归树可以看出递归的深度，每层的代价。

当 n==5 时的递归树如下。

从递归树可知每层的代价为它的结点个数，树的深度为 n(根节点为第1层)

递归的总代价为总节点个数，而递归的节点个数 以2ⁿ增长，所以该算法的时间复杂度为 O(2ⁿ)

空间复杂度分析

对单线程来说，递归的空间复杂度为：递归树的深度*每次递归所需要的空间

由递归树可知，递归的深度为n，每次递归所需时间为 O(1)

所以总的时间复杂度为 O(n*1) = O(n)