Leetcode | 从斐波那契数聊递归
题目信息
如果单纯的从难度上来讲，这题比较简单，我们只要根据题目的意思，转化为代码，注意一下边界情况即可，就能实现这道题。
class Solution { public int fib(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } return fib(n - 1) + fib(n - 2); } }
接着我们来聊聊递归：什么是递归呢？
就像上面的代码，这种在方法里面自己调用自己的操作，我们可以称之为递归。我们把这两个字拆开一下，“递”是进去，“归”是回来，有去有回，才是一个完整的递归过程。
你是否还记得，很久很久以前有这么一个故事：从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山.……
朋友们，有没有发现，和尚讲的这个故事可以一直循环下去，变成无解的死循环，除非故事中的一个和尚改口了。同样的道理，递归没有终止条件的情况下也会变成死循环，所以实现递归操作的时候要特别注意停止的标志。咱总不能一直付出吧，不然这递归要变成舔狗了～
简单的总结一下递归的一些特性：
- 可以把一个大的问题分解成一个或多个更小的问题，每个问题的解决逻辑是相同的。
- 大问题的结果依赖于这些小问题的结果
- 最小的问题有分解的临界值
如果你把上面的搞懂了，我们再来聊点复杂的。瞅一瞅上面的代码，你有没有发现一个问题，这里面出现了重复计算。
看上面的图片，所以这个优化空间是不是就出来了，我们是不是可以把重复计算的部分给优化掉？
此时就可以考虑使用数组存储一下已经计算出结果的值
参考代码：
class Solution { public int fib(int n) { // 处理临界值 if (n == 0) { return 0; } if (n == 1) { return 1; } // 创建缓存数组 int[] flags = new int[n + 1]; // 初始化缓存数组的值 Arrays.fill(flags, -1); flags[0] = 0; flags[1] = 1; // 开始递归 return getNum(n, flags); } public int getNum(int n, int[] flags) { // 如果不是初始值，说明这是个缓存值，可以直接返回 // 如果是初始值，就计算这个位置上的值，然后缓存起来 if (flags[n] == -1) { flags[n] = getNum(n - 1, flags) + getNum(n - 2, flags); } return flags[n]; } }
这样子会简化一部分操作，减少一些重复计算，时间从原来的8ms提升到现在0ms，真的是时间往前进了一大步。
我们再来拓展一下，递归本身在调用自己，直到遇到临界值。那么这么是不是可以转化为循环呢？
循环遍历数组，当前位置上的值就是之前位置上的值的和，遇到判断条件为false的时候，循环停止。
参考代码：
class Solution { public int fib(int n) { // 临界值的处理 if(n==0) return 0; // 记录缓存的数组，当n=0时，status[1]会出现数组越界，所以临界值0需要单独处理 int[] status = new int[n+1]; // 初始化 status[0] = 0; status[1] = 1; // 每次更新当前位置上的值，直接从前面的数组取值 for (int i = 2; i <= n; i++) { status[i] = status[i-1]+status[i-2]; } // 最后直接返回最后位置上的值 return status[n]; } }
同学们，有没有发现，上面三种实现，都表明了一件事。位置 n 上的值跟 n-1 和 n-2 位置上的值有关，那么我们是不是可以进一步优化代码呢？
假如我们只记录 n-1 和 n-2 位置上的值，这样是不是也能解决问题呢？
参考代码：
class Solution { public int fib(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } int a = 0; int b = 1; for (int i = 2; i <= n; i++) { int temp = a+b; a = b; b = temp; } return b; } }
从 LeetCode 的测试用例来说，这最后三种的解法在运行时间上没有差距。这道题本身就很简单，简单的细致化，最重要的是去从不同的角度去理解一些解题的思维逻辑。
