数据结构之递归

数据结构之递归

谨以此文纪念过往的岁月

对于数学函数(非负) 有f(0)=0并且f(x)=f(x-1)+x^2而言，则其递归程序如下：

1 int f(int x){

2       if(x==0)return 0;

3       else

4       return f(x-1)+x*x;

5 }

递归的四大准则：

1基准情形 必须总有一些不需要递归就可以计算的情形，即退出递归的条件。上面的(2)即是退出条件。

2不断的推进 即递归的程式经过的不断的退变，直至基准情况 。上面的(4) 即不断的向基准情况推进。

3 设计法则 假设所有的递归调用都能运行

4 合成效益法则 在求解一个问题的同一个实例时，切勿在不同的递归调用中做重复的工作。

上面的1,2,3都比较好理解，这第四个比较难搞一点。

想当年在学习递归时，我们是以常见的斐波那契数数列来学习递归的。

int f(int n){

         if(n <= 0)

                   return 0;

         if(n==1||n==2)return 1;

         else

                   return f(n-1)+f(n-2);

}

不过上面的递归不是一个好的方法，因为对于第四点他不满足。计算f(n)时需要计算f(n-1)和f(n-2),而计算f(n-1)时会计算f(n-2)和f(n-3),在不同递归中做了重复的f(n-2)计算。如何來改進該程式呢？

斐波那契数数列的數學函數是f(n)=f(n-1)+f(n-2) 式1,則f(n-1)=f(n-2)+f(n-3) 式2.

上述的式1減去式2得f(n)=2f(n-1)-f(n-3),其實現code如下：

int f(int n){

         if(n>3)return 2*f(n-1)-f(n-3);

         else if(n == 3) return 2;

         else if(n == 1||n ==2)return 1;

         else

                   return 0;          

}

對比上述的兩個code，可以發現code2會比code1少遞歸多次，其級數越高則其少遞歸次數越多。

遞歸在理解上比較好理解，但是在程式中卻不適合使用，因為遞歸會涉及到函數的調用，會頻繁的壓棧和出棧。當遞歸深度越深則速度越慢。

上面部份摘自：數據結構和算法分析