Java基础08

   递归算法是一种直接或者间接调用自身函数或者方法的算法。说简单了就是程序自身的调用。

递归算法就是将原问题缩小为相同的子问题，然后递归调用方法来表示 ，来解决问题。

递归算法，顾名思义就是有两个大的阶段：递和归，去（递去）和回（归来）。

斐波纳契数列又称黄金分割数列。

数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

因此就有如下代码

public class 斐波纳契数列 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int i = 10;
		int j = n(i);
		System.out.println(j);
	}

	public static int n(int k) {
		if (k == 1)
			return 1;
		if (k == 2)
			return 1;
		return k = n(k - 1) + n(k - 2);
	}

}

        汉诺塔问题是源于印度一个古老的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序放着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

将3个柱子分别认为A、B、C；

        （1） 把n-1个盘子从A 移到 B；

        （2） 把第n个盘子从 A移到 C；

　　 （3） 把n-1个盘子从B 移到 C；

如果是1个圆盘          次数为 2的1次方减1

　　　　　　　         2个圆盘的次数 2的2次方减1

这里我们不难发现，移到的步数必为奇数：

        （1）中间的一步是把最大的一个盘子从A移到C上去；

　　（2）中间一步之上可以看作把A上n-1个盘子通过借助辅助塔（C塔）移到了B上，

　　（3）中间一步之下可以看成作B上n-1个盘子通过借助辅助塔（A塔）移到了C上；

以此可以写出如下代码

public class 汉诺塔 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int i = 63;
		double j = n(i);
		System.out.println(j);
	}

	public static double n(double k) {
		if (k == 1)
			return 1;
		return k = 1 + 2 * n(k - 1);
	}

}