算法（一）：递归

算法（一）：递归

递归三大要素：

1. 明确你这个函数想要干什么
2. 寻找递归结束条件
3. 找出函数的等价关系式

案例1：斐波那契数列
案例2：小青蛙跳台阶
案例3：反转单链表

递归的优化：

案例2中，有非常非常多的子问题被重复计算
随着n的增大，重复计算的就越多，所以我们必须优化

优化思想：

将之前的计算结果保存起来，再次需要计算此结果时，先进行判断，看之前是否计算过
如果计算过，直接把先前保存过的计算结果取出来
如果没有计算过，再来进行递归计算

如何保存？

可用数组、Hashmap保存
以案例2为例：
我们用数组保存，n作为我们数组的下标，f(n)作为值，f(n)没有计算过的时候，让arr[n] = -1

//假定arr数组已经初始化好了
int f(int n){
    if(n <= 1){
        return n;
    }
    //先判断有没有计算过
    if(arr[n] != -1){
        //计算过，直接返回
        return arr[n];
    }else{
        //没有计算过，递归计算，并把结果保存到arr数组里
        arr[n] = f(n - 1) + f(n - 1);
        return arr[n];
    }
}

也就是说，使用递归的时候，必须要考虑有没有重复计算，如果重复计算了，一定要把计算过的状态保存起来

递归问题一般（并不都是）都是从上往下，直到递归到了最底层，然后一层层再把值返回
但是，当n比较大的时候，那么往下递归到n，才能将结果慢慢的返回，可能会导致栈空间不够用
这个时候考虑递推