当前位置: 首页 > >

数据结构算法---递归

发布时间:

一、递归思想
  递归的思想就是把一个问题分解成一个个的子问题和子子问题,然后这些子问题逐级返回,得到最终结果。
总结一下递归需要满足的几个条件:


    一个问题的解可以分解为几个子问题的解。问题与子问题,求解思路完全一样。存在递归终止条件。

二、斐波那契数列
 
  1.斐波那契数列: 斐波那契数列(Fibonacci sequence),又称*鸱指钍小⒁蚴Ъ伊邪耗啥?斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)
 
  2.代码实现


private static int febonacii(int index) {
//终止条件
if (index == 0) {
return 0;
}else if(index ==1){
return 1;
}else {
//递归
return febonacii(index - 1) + febonacii(index - 2);
}

}

3.结果:


febonacii(8)
34

三、汉诺塔
 1.汉诺塔游戏规则:把所有圆环从最左边的柱子移动到最右边的柱子(有三个柱子),每次只能移动一个盘子,大圆环不能压在小圆环上。
 2.分析:第一关

第二关:

第三关:

第四关:

通过上面演示可以分析得出以下结论:


    只有1个圆环则直接把圆环从from移动到to无论多少(n)个圆环都看成两个圆环(n-1)为一个圆环,n为最后一个圆环把n-1个圆环移动到中间柱子移动最后一个盘子到最右边的目标柱子把n-1个圆环从中间柱子移动到目标柱子

3.代码实现:


public static void hanoi(int n, String from, String in, String to) {
//只有一个圆环则直接把圆环从from移动到to
if (n == 1) {
System.out.println("第1个圆环从" + from + "移动到" + to);
}else {
//无论多少(n)个圆环都看成两个圆环(n-1)为一个圆环,n为最后一个圆环
//把n-1个圆环移动到中间柱子
hanoi(n-1,from,to,in);
//移动最后一个盘子到最右边的目标柱子
System.out.println("第"+n+"个圆环从" + from + "移动到" + to);
//把n-1个圆环从中间柱子移动到目标柱子
hanoi(n-1,in,from,to);
}

}

4.结果:


hanoi(4,"A","B","C");
第1个圆环从A移动到B
第2个圆环从A移动到C
第1个圆环从B移动到C
第3个圆环从A移动到B
第1个圆环从C移动到A
第2个圆环从C移动到B
第1个圆环从A移动到B
第4个圆环从A移动到C
第1个圆环从B移动到C
第2个圆环从B移动到A
第1个圆环从C移动到A
第3个圆环从B移动到C
第1个圆环从A移动到B
第2个圆环从A移动到C
第1个圆环从B移动到C



友情链接: