递归算法应该是经常会用到的一种，它能够把复杂问题用简单的代码实现。
但是递归理解起来不太容易，因为代码执行的过程有点“绕来绕去”，因此也不是特别容易搞懂
今天复习了一下递归算法，把我理解的过程复盘一下，另外我觉得每一种算法都有常规部分和高阶部分，在我看来能掌握常见的就行了，解决日常问题是首要目的
什么是递归呢？
简单的说就是要求解某个问题时，如果该问题可以拆解为相同求解过程的子问题，并且子问题仍然可以用相同的求解过程求解子子问题，那么就能够利用递归来求解
比如说数列求和：
1+2+3+4+5。
该问题可以拆解为 1+2+3+4，再 +5，那么前面的部分也可以看作为独立的求和过程。
然后又可以继续拆解为子子问题，求和：
1+2+3，再 +4。
归纳起来就是长度为 n 的数列，使用递归求和的话，为前 n-1 个数列的和加上第 n 个数
sum(n) = a[0], if n = 1
sum(n) = sum(n-1) + a[n], if n > 1
除了找到规律，提炼出递归的公式外，递归的另一个核心是递归的结束，也就是要找到一个终点，让递归停止继续循环，从而开始返回结果
比如上面的例子，如果没有给定终点的话，递归会无限循环下去，直到抛异常退出。
而这里的终点就是当 n=1 时，和就是该唯一元素的值
public static int sum(int[] array){
if (array == null || array.length == 0){
throw new IllegalArgumentException();
}
// 本递归的循环终点
if (array.length == 1){
return array[0];
}
int[] sub = Arrays.copyOf(array, array.length - 1);
return sum(sub) + array[array.length - 1];
}
另外，递归一个典型实现还有数学中的“斐波那契数列”，使用递归算法简直不要太简单
public static int fib(int n){
if (n == 0){
return 0;
}
if (n == 1){
return 1;
}
return fib(n-1) + fib(n-2);
}
递归算法在某些场景下，是非常简单的，但我们知道，有时候简单的代价就是耗时。
比如上面的斐波那契数列求解过程，可以画出如下的递归树：
其中每一个节点都会计算一次，那么 F(2) 这个节点就在这里被重复计算了 3 次，F(3) 被计算了 2 次。
这种反复求解相同的子问题，就称为具有重叠子问题。
这是递归算法效率没那么高的一大缺点。
那有人会说了，我把每一次计算的值都存起来，这样每次求解的时候判断一下，如果有这个值，直接取出来用，没有这个值再计算不就行了吗？
所以下面要提到的另一种算法：
“动态规划”就可以解决这种重复计算的场景，提高求解的效率
“动态规划”有两种方式，一种是采取存储的方式解决重复计算问题，这是自顶向下的，比如上面递归的方式添加一个存储数组用来存储计算过的值；
另一种是自底向上。
由于更多的时候用的是第二种方式，所以这里也只复盘这种方式。
还是以求和的例子来说，递归时，我们采取的是“倒推”的形式来得到结果，而动态规划则“正推”。
比如求和：
1+2+3+4+5，等价于先求出 1+2，再 +3+4+5，然后继续等价于 3+3，再 +4+5， 继续等价于 6+4，再 +5。
看出来了吧，其实就是把每一步的结果存起来，再用这个结果重复进行下一次计算，直到得到最后一个计算结果，那么该结果就是最后的和。
跟递归不同的是，动态规划要设定好起点值，然后从该值出发，去重复计算后面相同的过程，直到循环结束得到最后一个元素的值，就是最终结果
public static int dynamicSum(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException();
}
if (array.length == 1) {
return array[0];
}
int[] sum = new int[array.length - 1];
// 规划好起点
sum[0] = array[0] + array[1];
// 规划好重复的过程
for (int i = 1; i < array.length - 1; i++) {
sum[i] = sum[i - 1] + array[i + 1];
}
// 返回最后一个元素的值
return sum[sum.length - 1];
}
再来运用该算法解决“斐波那契数列”的计算。
“正推”则是，先计算 F(2), 再计算 F(3)，再计算 F(4)，直到算出 F(n-1)，就可以得到 F(n)。
先规划起点，是：
Fib = F(2)；
循环的重复过程是：
F(n-1)+F(n-2)
public static int dynamicFib(int n) {
if (n < 0) {
throw new IllegalArgumentException();
}
if (n == 0) {
return 0;
}
int[] fib = new int[n];
// n=1
fib[0] = 1;
// n=2，起点
fib[1] = 1;
// 循环重复的过程
for (int i = 2; i < n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
// 最后一个元素就是结果
return fib[fib.length - 1];
}
之前我讨论的“”，其中也有用到“动态规划”来实现，当时没有给出具体的实现，现在搞明白这些基本的原理后，也可以参考公式自己着手写出来了
动态规划的思想其实远不止上面谈到的这些，不过弄明白以上的部分，基本上日常的工作中就够对付了，如果你特别喜欢钻研更深入的原理的话，推荐看看《算法导论》，里面有对该算法更深入的描述，就这样。
