首页 > 代码库 > 递归讨论(一)

递归讨论(一)

前段时间刚看完c++语法部分的内容,现在开始着手研究下,用c++实现下一些基本的排序算法。恶魔 因为是初学者的缘故,可能理解之处还是存在不到位之处,但权且当作学习过程中的一种心得体会,也算记录下自己学习的路程吧。(理解的浅陋之处望及时指出)

所谓递归,就是方法自己调用自己,从而实现代码上的简化,同时也简化阅读人员的可读性。

递归的优势在于:当要求解一个问题时,在求解过程中,会碰到同样的处理过程。这个求解的过程就是递归的方法,不断递归的就是这个处理过程,而递归让这个问题逐渐变小,最终回到递归基上。

递归基:就是当问题足够简单时,或者已经不能再分解时,所能给出的返回结果,即为递归基。

这样说可能太抽象了,上例子了:微笑

比如:我们求解n!(n的阶乘),即1*2*3...n;

数学上:  f(n) = n*f(n-1);(n>=2,n是自然数),这个式子有个好名叫递推公式

可以看出:f(n)和f(n-1)它们是同样的问题,所以处理过程一定是一样的,只是规模上的问题。

该问题的详细过程:热烈的笑脸

当要求得f(n)时,我们要知道f(n-1),
求f(n-1)时,需求f(n-2)的值
...
最终要求f(1)的值,---------递归基的位置上

代码:
#include<iostream>int fun(int num);int main(){    using namespace std;    int num=5;    cout << fun(num);    return 0;}int fun(int num){    if(num==1)    {        return 1;    }    return num*fun(num-1);}

从上述代码可以看出,f(n)调用了f(n-1)的结果,同理f(n-1)会继续调用本身的方法,最终都会回归到递归基。
方法代码简化:狡猾

int fun(int num){    return num==1?1:num*fun(num-1);}

从上面的例子,我们初步了解了递归的形式。下面会展示一道典型的递归用法。

常谈的斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……

在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)

从递推公式中可以看出,它调用了自身,只是处理的规模变成了n-1和n-2;典型的递归式。

数列定义中可以看出递归基为:F(0)=0,F(1)=1;问题最终都会分解到递归基上。

上代码:

#include<iostream>int Fibonacci(int num);int main(){    using namespace std;    int num=5;    cout << Fibonacci(num);    return 0;}int Fibonacci(int num){    return num<=1?num:Fibonacci(num-1)+Fibonacci(num-2);}


程序还真是简单。
递归有个概略印象了,但程序并不是简洁就行了,还得运行起来快速。所以时间复杂度是必须考虑的,目前对空间复杂度方面暂时不考虑.
其运行图解如下图: 

005B4Iamty6NaydQAlwb6&690
我们根据递推公式:T(n) = T(n-1)+T(n-2)
这是一个常系数的二阶线性齐次递推关系式,其求解方法就简单了:
得出其特征方程:

clip_image001[7]
可以得到其解,呵呵,黄金分割数要出现了

clip_image001[9]

(黄金分割数的相反数哦。。。。。。)
从而得出复杂度如下:
 

clip_image001[13]

呵呵,我们平时只记个O(2^n),其实它的时间复杂度是这样的,很奇怪吧。但确实如此,可见此算法不是个高效的算法,当n达到一定的值时,出结果的速度会长达很久很久,举个例子吧,若n取100吧,2GHz的处理器,1s钟能处理2g次,即2^31次,而1年相当于2^25次方,所以n取100时,需要 2^(100-25-31)递归讨论(一)年,这得等多久啊。。。。。。。。。。

所以这不是一个合理的算法。。。。。。

分析上述高时间复杂度产生原因:有些已经计算过值,如F(5),在计算F(6)时,它会调用F(5),此时需重复计算F(5)的值,这样的多次的重复的计算,造就了如此高的时间复杂度。

若我们采取将这些计算过的值放在一个备忘表中,这样在下次调用中,直接从备忘表中取,我们可以瞬间降低时间开销。哈哈,是如此。

上述迭代是一种自上而下的算法,下面我们来看看自下而上的算法。

采用循环迭代的方法:

直接上代码:

#include<iostream>int Fibonacci(int num);int main(){    using namespace std;    int num=5;    cout << Fibonacci(num);    return 0;}int Fibonacci(int num){    int result=0;    int sum=1;    if(num<2)        return num;    int i=1;    while(i<num)    {        sum += result;        result = sum-result;        i++;    }    return sum;}

图解:

image

从上可以看出,有时递归并不是一定是解决问题最好的办法,有时也许循环迭代倒是处理问题的好方法

递归讨论(一)