递归的一般写法

参考文章

• https://segmentfault.com/a/1190000013861208
• https://blog.csdn.net/mingzhentanwo/article/details/50992743

重点把控两个要素：

• 递归的出口
• 递归的表达式规律

关键点

• 找到问题出口
• 将当前问题 转换为 一个小的问题，找到规律；在递归中常常是将问题切割成两个部分(1和整体的思想)，这能够让我们快速找到递归表达式(规律)

一般模板

Result M(Problem prob) {
    if(problem can be solved easily) {
        return <easy solution>;
    }
    Problem smaller1 = <reduce problem to smaller problem>;
    Problem smaller2 = <reduce problem to smaller problem>;
    Result finalResult = <combine all results of smaller problem to slove large problem>;
    return finalResult;
}

体会一下如何将问题切割成两个部分(1和整体的思想)，快速找到递归表达式(规律)

计算1 + 2 + 3 + …… + 100；sum(n)的问题转换为了sum(n-1) + n

    public static void main(String[] args) {
        System.out.println("公众号：Java3y：" + sum(100));
    }
    /**
     *
     * @param n 要加到的数字，比如题目的100
     * @return
     */
    public static int sum(int n) {
        if (n == 1) {
            return 1;
        } else {
            return sum(n - 1) + n;
        }
    }

再看个数组相关的递归的一般写法

  public static void main(String[] args) {
        int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};
        System.out.println("公众号：Java3y：" + findMax(arrays, 0, arrays.length - 1));
    }
    /**
     * 递归，找出数组最大的值
     * @param arrays 数组
     * @param L      左边界，第一个数
     * @param R      右边界，数组的长度
     * @return
     */
    public static int findMax(int[] arrays, int L, int R) {
        //如果该数组只有一个数，那么最大的就是该数组第一个值了
        if (L == R) {
            return arrays[L];
        } else {
            int a = arrays[L];
            int b = findMax(arrays, L + 1, R);//找出整体的最大值
            if (a > b) {
                return a;
            } else {
                return b;
            }
        }
    }