什么是递归算法

这篇文章主要介绍“什么是递归算法”，在日常操作中，相信很多人在什么是递归算法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”什么是递归算法”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

递归求斐波那契数列的性能分析

先来看一下求斐波那契数的递归写法。

int fibonacci(int i) {        if(i <= 0) return 0;        if(i == 1) return 1;        return fibonacci(i-1) + fibonacci(i-2); }

对于递归算法来说，代码一般都比较简短，从算法逻辑上看，所用的存储空间也非常少，但运行时需要内存可不见得会少。

时间复杂度分析

来看看这个求斐波那契的递归算法的时间复杂度是多少呢?

在讲解递归时间复杂度的时候，我们提到了递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归的时间复杂度。

可以看出上面的代码每次递归都是O(1)的操作。再来看递归了多少次，这里将i为5作为输入的递归过程 抽象成一颗递归树，如图：

从图中，可以看出f(5)是由f(4)和f(3)相加而来，那么f(4)是由f(3)和f(2)相加而来 以此类推。

在这颗二叉树中每一个节点都是一次递归，那么这棵树有多少个节点呢?

我们之前也有说到，一棵深度(按根节点深度为1)为k的二叉树最多可以有 2^k - 1 个节点。

所以该递归算法的时间复杂度为 O(2^n) ，这个复杂度是非常大的，随着n的增大，耗时是指数上升的。

来做一个实验，大家可以有一个直观的感受。

以下为C++代码，来测一下，让我们输入n的时候，这段递归求斐波那契代码的耗时。

#include <iostream> #include <chrono> #include <thread> using namespace std; using namespace chrono; int fibonacci(int i) {        if(i <= 0) return 0;        if(i == 1) return 1;        return fibonacci(i - 1) + fibonacci(i - 2); } void time_consumption() {     int n;     while (cin >> n) {         milliseconds start_time = duration_cast<milliseconds >(             system_clock::now().time_since_epoch()         );          fibonacci(n);          milliseconds end_time = duration_cast<milliseconds >(             system_clock::now().time_since_epoch()         );         cout << milliseconds(end_time).count() - milliseconds(start_time).count()             <<" ms"<< endl;     } } int main() {     time_consumption();     return 0; }

根据以上代码，给出几组实验数据：

测试电脑以2015版MacPro为例，CPU配置：2.7 GHz Dual-Core Intel Core i5

测试数据如下：

• n = 40，耗时：837 ms

• n = 50，耗时：110306 ms

可以看出，O(2^n)这种指数级别的复杂度是非常大的。

所以这种求斐波那契数的算法看似简洁，其实时间复杂度非常高，一般不推荐这样来实现斐波那契。

其实罪魁祸首就是这里的两次递归，导致了时间复杂度以指数上升。

return fibonacci(i-1) + fibonacci(i-2);

可不可以优化一下这个递归算法呢。主要是减少递归的调用次数。

来看一下如下代码：

// 版本二 int fibonacci(int first, int second, int n) {     if (n <= 0) {         return 0;     }     if (n < 3) {         return 1;     }     else if (n == 3) {         return first + second;     }     else {         return fibonacci(second, first + second, n - 1);     } }

这里相当于用first和second来记录当前相加的两个数值，此时就不用两次递归了。

因为每次递归的时候n减1，即只是递归了n次，所以时间复杂度是 O(n)。

同理递归的深度依然是n，每次递归所需的空间也是常数，所以空间复杂度依然是O(n)。

代码(版本二)的复杂度如下：

• 时间复杂度：O(n)

• 空间复杂度：O(n)

此时再来测一下耗时情况验证一下：

#include <iostream> #include <chrono> #include <thread> using namespace std; using namespace chrono; int fibonacci_3(int first, int second, int n) {     if (n <= 0) {         return 0;     }     if (n < 3) {         return 1;     }     else if (n == 3) {         return first + second;     }     else {         return fibonacci_3(second, first + second, n - 1);     } }  void time_consumption() {     int n;     while (cin >> n) {         milliseconds start_time = duration_cast<milliseconds >(             system_clock::now().time_since_epoch()         );          fibonacci_3(0, 1, n);          milliseconds end_time = duration_cast<milliseconds >(             system_clock::now().time_since_epoch()         );         cout << milliseconds(end_time).count() - milliseconds(start_time).count()             <<" ms"<< endl;     } } int main() {     time_consumption();     return 0; }

测试数据如下：

• n = 40，耗时：0 ms

• n = 50，耗时：0 ms

大家此时应该可以看出差距了!!

空间复杂度分析

说完了这段递归代码的时间复杂度，再看看如何求其空间复杂度呢，这里给大家提供一个公式：递归算法的空间复杂度 = 每次递归的空间复杂度 *  递归深度

为什么要求递归的深度呢?

因为每次递归所需的空间都被压到调用栈里(这是内存管理里面的数据结构，和算法里的栈原理是一样的)，一次递归结束，这个栈就是就是把本次递归的数据弹出去。所以这个栈最大的长度就是递归的深度。

此时可以分析这段递归的空间复杂度，从代码中可以看出每次递归所需要的空间大小都是一样的，所以每次递归中需要的空间是一个常量，并不会随着n的变化而变化，每次递归的空间复杂度就是O(1)。

在看递归的深度是多少呢?如图所示：

递归第n个斐波那契数的话，递归调用栈的深度就是n。

那么每次递归的空间复杂度是O(1)， 调用栈深度为n，所以这段递归代码的空间复杂度就是O(n)。

int fibonacci(int i) {        if(i <= 0) return 0;        if(i == 1) return 1;        return fibonacci(i-1) + fibonacci(i-2); }

最后对各种求斐波那契数列方法的性能做一下分析，如题：

可以看出，求斐波那契数的时候，使用递归算法并不一定是在性能上是最优的，但递归确实简化的代码层面的复杂度。

二分法(递归实现)的性能分析

带大家再分析一段二分查找的递归实现。

int binary_search( int arr[], int l, int r, int x) {     if (r >= l) {         int mid = l + (r - l) / 2;         if (arr[mid] == x)             return mid;         if (arr[mid] > x)             return binary_search(arr, l, mid - 1, x);         return binary_search(arr, mid + 1, r, x);     }     return -1; }

都知道二分查找的时间复杂度是O(logn)，那么递归二分查找的空间复杂度是多少呢?

我们依然看 每次递归的空间复杂度和递归的深度

首先我们先明确这里的空间复杂度里面的n是什么?二分查找的时候n就是指查找数组的长度，也就是代码中的arr数组。

每次递归的空间复杂度可以看出主要就是参数里传入的这个arr数组，即：O(n)。

再来看递归的深度，二分查找的递归深度是logn ，递归深度就是调用栈的长度，那么这段代码的空间复杂度为 n * logn = O(nlogn)。

有同学问了：为什么网上很多人说递归二分查找的空间复杂度是O(logn)，而不是O(nlogn)呢?

其实还是因为这个数组，我们可以把这个数组放到外面而不是放在递归函数参数里里，代码如下：

int arr[] = {2, 3, 4, 5, 8, 10, 15, 17, 20}; int binary_search(int l, int r, int n) {     if (r >= l) {         int mid = l + (r - l) / 2;         if (arr[mid] == n)             return mid;         if (arr[mid] > n)             return binary_search(l, mid - 1, n);         return binary_search(mid + 1, r, n);     }     return -1; }

看这份代码将arr数组定义为全局变量，而不放在递归循环里，那么每层递归的空间复杂度是O(1)，递归深度为O(logn)，整体空间复杂度为 1 * logn  = O(logn)。

到此，关于“什么是递归算法”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！