`
stinge
  • 浏览: 148532 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

递归法

阅读更多

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

 

注意:

  (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);
}
 

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics