递归——基础练习

1、递归设计经验

• 找重复——子问题
• 找重复中的变化量——参数
• 找参数的变化趋势——出口

2、算法题

  Java 代码实现：

 1. 求阶乘

 2. 打印 i 到 j 的数字

 3. 数组求和

 4. 翻转字符串

 5. 斐波那契数列

 6. 最大公约数

 7. 插入排序改递归

 8. 汉诺塔

 9. 二分查找递归形式

 10. 小白上楼梯

1）求阶乘

  求阶乘 x 的阶乘：1 * 2 * 3 * 4 * 5 * ... * x。

    public static int factorial(int i) {
        if (i == 1) {
            return 1;
        }
        return i * factorial(i - 1);
    }

2）打印 i 到 j 的数字

    public static void printing(int i, int j) {
        System.out.println(i);
        if (i == j) {
            return;
        }
        printing(i + 1, j);
    }

3）数组求和

  求数组的和，index 表示数组的开始下标，第一次传入 0。

    public static int sum(int[] array, int index) {
        if (index == array.length - 1) {
            return array[index];
        }
        return array[index] + sum(array, index + 1);
    }

4）翻转字符串

  翻转字符串 index 表示字符串的最大下标，长度为 3 的字符串传入 2。

    public static String reversal(String src, int index) {
        if (index == 0) {
            return "" + src.charAt(index);
        }
        return src.charAt(index) + reversal(src, index - 1);
    }

5）斐波那契数列

  斐波那契数列 1+1+2+3+5+8，index 表示指定位置。

    public static int fibonacciSequence(int index) {
        if (index == 1 || index == 2) {
            return 1;
        }
        return fibonacciSequence(index - 1) + fibonacciSequence(index - 2);
    }

6）最大公约数

  求 a 和 b 的最大公约数，则 a 必须大于 b。最小公倍数等于 a 乘 b 的积除以最大公约数。

    public static int maximumDivisor(int a, int b) {
        if (b == 0) {
            return a;
        }
        return maximumDivisor(b, a % b);
    }

7）插入排序改递归

  对数组排序就是将数组中下标为 0 到倒数第一个的数进行排序。等价于：对数组中下标为 0 到倒数第二个的数进行排序，然后把最后一个元素插入到这个有序数组中。insert 的初值为 array.length-1。

    public static void sort(int[] array, int insert) {
        if (insert == 0) {
            return;
        }
        // 将 insert 下标之前的数顺序排好
        sort(array, insert - 1);
        int temp = array[insert];
        int index = insert - 1;
        // 如果 temp 小于数组index下标的数则将temp插入该数前面
        while (index > -1 && temp < array[index]) {
            array[index + 1] = array[index];
            index--;
        }
        array[index + 1] = temp;
    }

8）汉诺塔

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

  题意：将 A 柱子上的所有圆盘移动到 B 柱子上，即将 N 个圆盘从 A 柱子移动到 B 柱子，C 柱子作为辅助。

等价于：

1. N-1 个圆盘从 A 移动到 C，B 为辅助。
2. 将第 N 个圆盘从 A 移动 B。
3. 将 N-1 个圆盘从 C 移动 B，A 为辅助。

    /**
     * 将N个圆盘从A移动到B，C作为辅助
     *
     * @param n    表示N个圆盘
     * @param from 表示A，起点
     * @param to   表示B，终点
     * @param help 表示C，辅助
     */
    public static void towerOfHanoi(int n, String from, String to, String help) {
        // 如果只剩一个圆盘，则直接将该圆盘移动到指定位置即可。
        if (n == 1) {
            System.out.println("将 " + n + " 从 " + from + " 移动到 " + to);
            return;
        }
        // 将n-1个圆盘移动到辅助柱子上
        towerOfHanoi(n - 1, from, help, to);
        // 将第n个盘子移动到指定位置
        System.out.println("将 " + n + " 从 " + from + " 移动到 " + to);
        // 将n-1个圆盘从辅助盘上移动到指定位置
        towerOfHanoi(n - 1, help, to, from);
    }

9）二分查找递归形式

  二分查找用于查找一个数在一个有序数组中的下标。

思路：折半后的指针索引和被查找元素比较。

1. 如果元素 > 中间索引上的元素，则小指针 = 中间指针 +1。
2. 如果元素 < 中间索引上的元素，则大指针 = 中间指针-1。
3. 如果小指针索引 > 大指针索引，则没有找到，结束查找。
4. 如果元素 == 数组中索引上的元素，则返回中间索引，结束查找。

    public static int binarySearch(int[] array, int number, int max, int min) {
        if (min > max) {
            return -1;
        }
        int middle = (max + min) / 2;
        if (number > array[middle]) {
            return binarySearch(array, number, max, middle + 1);
        } else if ((number < array[middle])) {
            return binarySearch(array, number, middle - 1, min);
        } else {
            return middle;
        }
    }

10）小白上楼梯

  小白正在上楼梯，楼梯有n阶台阶，小白一次可以上一阶，二阶或者三阶，实现一个方法，计算小白有多少种走完楼梯的方式。

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