数据结构与算法–递归（Recursion Algorithm）

什么是递归算法？

把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解（基本问题），从而得到原来问题的解。

哪时候用递归算法？

总是尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况
总有一个最简单的情况，也就是递归结束的条件，一般是第一条语句if(xx) return
递归调用的父问题和尝试解决的子问题之间不应该有交集。

递归的优缺点

优点：

代码更加简洁：代码一般都是对基本问题的求解，逻辑简单
扩展性高：如果新增功能，可按照同样的抽象逻辑进行扩展

缺点：

效率不足：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址以及临时变量，这些都需要空间；而往栈中压入数据和弹出数据都需要时间
重复计算：由于是把一个问题进行分解成多个小问题，多个小问题之间存在相互重叠的部分，就存在重复计算问题。例如fibonacci斐波那契数列的递归实现
栈溢出（Stack Overflow）：每一次函数调用都需要入栈，而如果当递归调用的层次太深，就会超出栈的最大容量，导致栈溢出

递归算法示例

假设我们要实现一个数组求和，如果用递归算法实现

第一步：定义问题

分解成小问题就是：当前相加的和 + 下一个元素
结束条件（最基本问题，无法继续递归了）：没有下一个元素或下一个元素已经到了数组的末尾

以上两个逻辑无论对哪个小问题都能满足

第二步：算法实现

public class ArraySum {

    /**
     * 数组求和，用户调用的公开方法。
     *
     * @param arr
     * @return
     */
    public static int sum(int[] arr) {
        // 默认从0元素开始求和
        return sum(arr, 0);
    }

    /**
     * 递归算法，私有方法。
     * <p>
     * 计算arr[left...n)这个区间内所有数字的和。即left到n-1这些索引区间的和。
     *
     * @param arr  数组
     * @param left 左边界的点，其实是一个索引
     * @return 和
     */
    private static int sum(int[] arr, int left) {
        // 首先判断，left等于数组长度的时候，说明递归到了最后
        if (left == arr.length) {
            return 0;
        } else {
            // 递归调用方式来求下一个小问题：sum(arr, left + 1);
            return arr[left] + sum(arr, left + 1);
            // 我们计算从left到n这个区间范围内的所有元素的和，变成了计算从left+1到n所有数字的和。
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        int sum = ArraySum.sum(arr);
        System.out.println("数组之和： " + sum);
    }
}