今天小编整理了下以前自学过的算法知识，对于递归算法的使用也有点体会。这里就举个例子分享一下。
“假设第1个月有 1 对刚诞生的兔子，第 2 个月进入成熟期，第 3 个月开始生育兔子，而1 对成熟的兔子每月会生 1 对兔子，兔子永不死去……那么，由 1 对初生兔子开始，12 个月后会有多少对兔子呢？”
这个问题就是神奇兔子数列也就是斐波那契数列，分析下可发现该数列具有如下的特征：
n<3时，f(n)=1;
n>2时，f(n)=f(n-1)+f(n-2)；
大多数人都是采用递归表达式设计这样的一个算法，截图如下：
递归实现
我们把该算法的时间复杂度记为T(n)
n=1时，T(n)=1；【此时执行一次return语句程序步为1】
n=2时，T(n)=1；【此时执行一次return语句程序步为1】
n=3时，T(n)=3；【调用Fib(2)、Fib(1)和执行一次加法运算 Fib(2)+Fib(1)，程序步数为3】
依此类推得到T(n)=T(n-2)+T(n-1)+1
由此可见，f(n)<T(n)。只要求解出斐波那契数列的通项公式，就可得到T(n)。
接下来我们来求f(n)。
首先这是一个二阶线性递推数列，可采用特征方程法。由于简书的局限性，故小编将求解过程用word整理后进行截图，过程若有误请指出，截图如下：
因此我们可以得到该算法的时间复杂度T(n)是指数级的，也就是2的n次幂。因此我们可以把该递归函数看成爆炸增量函数。随着n的增长，这个算法会不会“爆掉”？经常见到有些算法调试没问题，运行一段也没问题，但关键的时候宕机。例如，在线考试系统，50 个人考试没问题，100 人考试也没问题，如果全校 1 万人考试就可能出现宕机。像用递归实现的这个斐波那契数列算法，如果n的值为50时，那么该函数要执行2的50次幂步，在一台每秒可以运算十亿步的计算机上，也要执行13天。如果n=60，就要执行310.56年。因此 指数阶时间复杂度运行效率极差，编写算法要极力避开这种做法。在这里我们可以简单的对该递归程序进行改动，降低算法的时间复杂度。将上面的算法改进如下所示：
非递归实现
可以分析发现该算法的时间复杂度降低为O(n)。其实我们还可以继续降阶，使算法时间复杂度更低，降到对数阶 O(logn)。斐波那契数列采用递归算法实现除了时间复杂度高，还有一个关键的因素就是其空间复杂度也高，在函数调用过程中会占用大量的堆栈。因此对于大规模的数据而言，采用递归的算法也是要避免的。
这是小编的一点分享，欢迎指正错误。
网友评论