数据结构之：递归思想

    public static int fib(int N) {
        if (N == 1) return 1;
        if (N == 2) return 1;
        System.out.println("求第" + N + "个月的兔子数量");
        System.out.println("转化为求第" + (N - 1) + "个月和第" + (N - 2) + "个月的兔子数量");
        return fib(N - 1) + fib(N - 2);
    }

大部分递归 可以转化为迭代处理

Make it work,Make it right,Make it fast

思路：使用数组存储，通过 n-1 和 n-2 的值进行计算

    public static int fib1(int N) {
        // 6 —— 0 1 2 3 4 5
        // fib(0) = 0 有时需要处理
        if (N <= 1) return 1;
        int[] arr = new int[N];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[N - 1];
    }

印度的恒河 瓦拉那西 诞生婆罗门教

放了三根柱子，其中一个根柱子上放了 64 个圆盘

需要将全部圆盘 移动到另一根柱子上

并且 每次只能移动一个 移动过程中 小圆盘必须在大圆盘之上

为何不可完成？

分析：

一个圆盘 A->C

两个圆盘 A->B A->C B->C

三个圆盘 A->C A->B C->B ( 把前两个圆盘 从 A 移动到 B)

A->C ( 移动最大的圆盘 )

B->A B->C A->C ( 再把前两个圆盘 从 B 移动到 C)

N 个圆盘

先把前 N-1 个圆盘 从 A 移动到 B ( 经由 C)

再把最大的圆盘 从 A 移动到 C

最后把前 N-1 个圆盘 从 B 移动到 C ( 经由 A)

移动次数

H(1) = 1

H(2) = 3

H(3) = H(2) + 1 + H(2) = 7

H(4) = 7 + 1 + 7 = 15

H(N) = H(N-1) + 1 + H(N-1) = 2^N - 1

// 四个参数 有n个圆盘 需要从A柱子移动到C 经由B
// 起始 中间 终点
public static void hanoi(int n, char A, char B, char C) {
// 出口
if (n == 1) {
System.out.println(A + "->" + C);
return;
}
// 先把前N-1个圆盘 从A移动到B (经由C)
// 再把最大的圆盘 从A移动到C
// 最后把前N-1个圆盘 从B移动到C (经由A)
hanoi(n - 1, A, C, B);
System.out.println(A + "->" + C);
hanoi(n - 1, B, A, C);
}

public class Fibonacci {
 
 
    public static void main(String[] args) {
        System.out.println(fib1(6));
    }
 
    // 返回第n个月有多少只兔子
    public static int fib(int N) {
        if (N == 1) return 1;
        if (N == 2) return 1;
        System.out.println("求第" + N + "个月的兔子数量");
        System.out.println("转化为求第" + (N - 1) + "个月和第" + (N - 2) + "个月的兔子数量");
 
        return fib(N - 1) + fib(N - 2);
    }
 
 
    public static int fib1(int N) {
        // 6 —— 0 1 2 3 4 5
        // fib(0) = 0  有时需要处理
        if (N <= 1) return 1;
        int[] arr = new int[N];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[N - 1];
    }
}

public class Hanoi {
 
    public static void main(String[] args) {
        //三个圆盘  A->C   A->B  C->B (把前两个圆盘 从A移动到B)
        //         A->C  (移动最大的圆盘)
        //         B->A  B->C  A->C (再把前两个圆盘 从B移动到C)
        hanoi(3, 'A', 'B', 'C');
    }
 
    // 四个参数  有n个圆盘  需要从A柱子移动到C  经由B
    //                                  起始    中间     终点
    public static void hanoi(int n, char A, char B, char C) {
        // 出口
        if (n == 1) {
            System.out.println(A + "->" + C);
            return;
        }
 
        //    先把前N-1个圆盘  从A移动到B (经由C)
        //    再把最大的圆盘  从A移动到C
        //    最后把前N-1个圆盘  从B移动到C (经由A)
        hanoi(n - 1, A, C, B);
        System.out.println(A + "->" + C);
        hanoi(n - 1, B, A, C);
    }
}