递归法

递归：一个过程直接或间接的调用自己

 

注意：

　　(1) 递归就是在过程或函数里调用自身;

　　(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

 

　递归算法一般用于解决三类问题：

 

      (1) 数据的定义是按递归定义的。(Fibonacci函数)

　　(2) 问题解法按递归算法实现。(回溯)

　　(3) 数据的结构形式是按递归定义的。(树的遍历，图的搜索)

 

　　递归的缺点：

　　递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

 

     递归设计：

      （1）对原问题S进行分析，假设出合理的叫嚣的问题S1；

      （2）假设S1是可解的，再此基础上确定S的解，即给出S与S1的关系；

      （3）确定一个特定的可解情况，作为递归的出口。

 

   递归向非递归转换：

      （1）直接转换法：可以直接求值，不需要回溯，使用中间变量来保存中间结果

      （2）间接转换法：使用栈 来保存中间结果。

 

//阶乘，递归
public static int jiecheng(int n){
	if(n > 1){
		return jiecheng(n-1) * n;
	}else{
		return 1;
	}
}
//阶乘，非递归
public static int jiecheng1(int n){
	int s = 1;
	for(int i = 1; i <=n; i++){
	s = s*i; 	
	}
	return s;
}

 

//汉诺塔问题
public static void hanoi(int n, char a, char b, char c){
	//结束条件，剩最后一个
	if(n == 1){
		//当剩最后一个时，将a上的盘移动到c上
		move(a,1,c);
	}else{
		/*将n-1个从a移到b上，然后将最后一个移动到c上，
		再以a为空柱，将b上的n-1个移动到c上
		*/
		hanoi(n-1,a,c,b);
		move(a,n,c);
		hanoi(n-1,b,a,c);
	}
}
public static void move(char a, int n, char c){
	System.out.println("从"+a+"移动到"+c);
}