1. 方法递归调用规则
2. 方法递归练习
2.1 请用递归的方式求出斐波那契数 219
//请使用递归的方式求出斐波那契数 1,1,2,3,5,8,13...给你一个整数 n，求出它的值是多少
public class Test28
{
public static void main(String[] args)
{
T t1 = new T();
int n = 7;
int ret = t1.fibonacci(n);
if(ret != -1)
{
System.out.println("当n="+n+"时对应的斐波那契数="+ret);
}
}
}
class T
{
//思路分析
//1. 当 n = 1 斐波那契数 是 1
//2. 当 n = 2 斐波那契数 是 1
//3. 当 n >= 3 斐波那契数 是前两个数的和
//4. 这里就是一个递归的思路
public int fibonacci(int n)
{
if(n>=1)
{
if(n==1||n==2)
{
return 1;
}
else
{
return fibonacci(n-1)+fibonacci(n-2);
}
}
else
{
System.out.println("输入错误,n>=1");
return -1;
}
}
}
2.2 猴子吃桃问题 220
猴子吃桃子问题：有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！以后每天猴子都吃其中的一半，然后再多吃一个。当到第 10 天时， 想再吃时（即还没吃），发现只有 1 个桃子了。问题：最初共多少个桃子？
public class Test28
{
public static void main(String[] args)
{
T t1 = new T();
int day = 9;
int ret = t1.peach(day);
if(ret != -1)
{
System.out.println("第"+day+"天有"+ret+"个桃子");
}
}
}
class T
{
//思路分析
// 逆推 1. day = 10 时 有 1 个桃子
// 2. day = 9 时 有 (day10 + 1) * 2 = 4
// 3. day = 8 时 有 (day9 + 1) * 2 = 10
// 4. 规律就是 前一天的桃子 = (后一天的桃子 + 1) *2
// 5. 递归
public int peach(int day)
{
if(day==10)//第10天 只有一个桃
{
return 1;
}
else if(day>=1&&day<=9)
{
return (peach(day+1)+1)*2;
}
else
{
System.out.println("day在1-10");
return -1;
}
}
}
3. 汉诺塔
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，
在一根柱子上从下往上按照大小顺序摞着 64 片圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一
根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
假如每秒钟移动一次，共需多长时间呢？移完这些金片需要 5845.54 亿年以上，太阳系的预期寿命据说也就是数百亿年。
真的过了 5845.54 亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭
//汉诺塔 225
public class Test28
{
public static void main(String[] args)
{
Tower t1 = new Tower();
t1.move(3,'A','B','C');
}
}
class Tower
{
public void move(int num,char a,char b,char c)
{
//num 表示要移动的个数, a, b, c 分别表示 A 塔，B 塔, C 塔
if(num==1)//假如只有一个盘
{
System.out.println(a+"->"+c);
}
else//如果有多个盘，可以看成两个 , 最下面的和上面的所有盘(num-1)
{
//(1)先移动a上面所有的盘到 b, 借助 c
move(num-1,a,c,b);
//(2)把最下面的这个盘，移动到 c
System.out.println(a+"->"+c);
//(3)再把 b 塔的所有盘，移动到 c ,借助 a
move(num-1,b,a,c);
}
}
}
