近期在论坛上看到很多求递归算法,我总结了一些与递归有关的知识.与大家分享一下,避免在使用递归时的疑惑.
首先,我只注重效率,如果涉及效率的会比较多.我也只解过几个递归题目.经验有限.
一个简单的例子.
public static int getSum(int max,int n,int i){
  max+=i;
  if(n==0)
   return max;
  else return getSum(max,n-1,i+1);
}
这是我以一个最笨的方式实现的for循环转递归算法.它的效率肯定是很低的.但是却很容易理解递归的原理.
因为我们都很懂for循环,有任何题目,绝对最先想出的是for循环而不是递归.除非很熟练,不然否则很多用for循环很简单
求解的题,用递归却想半天想不出结果.
我说一下自己总结的for循环转递归的方法
首先用递归明确这几点,1:是结束条件.2:是推进条件.其次,在我们用常规for循环或是while求解时,有哪些是变量是参与运算的.
递归很麻烦.它内部参与运算的值,如果定义在递归内,开始计算,就没有意义了.
我在起初完全没有头绪时,就用这种方式清晰思路

for循环条件:arr[]	max	int i	i<arr.length		i--	if(max<arr		max=arr[i
arr[]	max=arr[0]	length--	max<arr[length]
for循环转递归,是将其条件转换.将循环内的条件,用方法参数代替
for循环结束条件:i==arr.length-1;
递归结束条件:length=0;
递归内有些条件在递归过程中必须保持原值的.就要加到参数列表中. 比较搞笑,但是有效. 后来就因为一直研究程序效率.在使用递归时,发现了递归的一个弊端

1. public static int getSum(int years) {//这个很复杂,但是解法,却可以很简单.
   
2.         if (years == 0)
   
3.                         return 0;
   
4.                 else if (years >= 1 && years <= 3)
   
5.                         return 1;
   
6.                 else if (years > 3)
   
7.                         return getSum(years - 2) + getSum(years - 3) + getSum(years - 4);
   
8.                 else
   
9.                         System.out.println("输入有误，请重新输入！");
   
10.                 return years;
    
11.         }

复制代码

1. public static int fib(int n){这个与上面无关.同样是一个递归应用.
   
2.         if(n<=1)
   
3.                         return 1;
   
4.                 else return fib(n-1)+fib(n-1);
   
5.         }

复制代码

它们有一个共同点:在递归语句内,使用了多重递归语句.这是要命的一种解法.
最上面的例子:相当一个三层嵌套for循环.
下面的相关于:双层.
如果是直接使用循环,可以很直观的发现.但是使用递归.很少有人意识到这其中的效率问题.
下面是一个for循环的解题思路:

1. public static double getCattleCount(int n){//同题上面的三层递归.但是用for循环只循环n-3次.
   
2.         double sum=0;
   
3.                 double first=1;
   
4.                 double second=1;
   
5.                 double thread=1;
   
6.                 for(int i=0;i<n-3;i++){
   
7.                         sum=first+thread;
   
8.                         first=second;
   
9.                         second=thread;
   
10.                         thread=sum;
    
11.                 }
    
12.                 if(n<=3)
    
13.                         return 1;
    
14.                 else return sum;
    
15.         }

复制代码

所以效率出来了:
/*for循环:50          1000
  83316385      4.239507006748923E165
  0毫秒                    31毫秒*/
递归:50                1000
      536毫秒         超过5分钟
所以使用递归,不仅只有那起始的两个基本原则,应该加上这一点:
绝对的递归次数.如果不能比使用for循环次数更少.就避免使用递归.否则就是适得其反.
高人的递规示例:

1. /**高效的pow算法
   
2.         */
   
3.         public static long pow(long x,int n){
   
4.                 System.out.println("n="+n);
   
5.                 if(n==0)
   
6.                         return 1;
   
7.                 if(n%2==0)
   
8.                         return pow(x*x,n/2);
   
9.                         else  return pow(x*x,n/2)*x;
   
10.         }

复制代码

这种使用递归,能高效的解决求一个数的多次方的问题
且看递归次数:
n=62 n=31 n=15 n=7 n=3 n=1 n=0 4611686018427387904
只需要:7次便可以求解出2的62次方:超过62次方,以后因为数太大,所以结果会异常,但这种解法,数越大.效率越高.
n=6200 n=3100 n=1550 n=775 n=387 n=193 n=96 n=48 n=24 n=12 n=6 n=3 n=1 n=0 0
6200次方,仅需:14次解出.由于超出long的范围,所以结果为0
好了,差不多了.如果大家有好的思路,一起交流交流,
国际惯例,散币

楼主很厉害。先占位，再仔细看。

好东西 慢慢看

最近就方法的递归调用正加强练习，递归调用在工作中用的还是挺多的。帖子不错，好好看看...

好东西。。。。