在我前面的文章举例了几个递归案例， 递归案例.
首先来来看第一一个例子，斐波那契数列。原题见链接: 剑指 Offer 10- I. 斐波那契数列 . 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、…… 斐波那契数列以如下被以递推的方法定义： F ( 1 ) = 1 ， F ( 2 ) = 1 , F ( n ) = F ( n − 1 ) + F ( n − 2 ) （ n ≥ 3 ， n ∈ N ∗ ） F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N^*） F(1)=1，F(2)=1,F(n)=F(n−1)+F(n−2)（n≥3，n∈N∗） 代码实现如下
private final int model = 1000000007; int[] memoryAraray; public int fib(int n) { if (n < 2){ return n; } return ((fib(n - 1) % model + fib(n - 2) % model )) % model; }上述代码提交后，会发现到计算到41时，已经超出时间限制，原因在于会重复计算已经出现的值，所以递归的最大缺点就是大量的重复计算，时间复杂度高。（具体可见力扣上的题解）
可知，在递归过程中会重复计算已经出现的值，那么此时可以建立一个“记忆”数组来储存已经递归出来的值。如果当前值已经在数组中了就直接返回，无需再计算。
原理： 在递归法的基础上，新建一个长度为 nn 的数组，用于在递归时存储 f(0)f(0) 至 f(n)f(n) 的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。缺点： 记忆化存储需要使用 O(N)O(N) 的额外空间。其实就是以空间换时间，改进代码如下：
private final int model = 1000000007; int[] memoryAraray; public int fib(int n) { memoryAraray = new int[n + 1]; return memory(n); } public int memory(int n) { if (n < 2) { return n; } if (memoryAraray[n] != 0) { return memoryAraray[n]; } int ans = 0; ans = ((memory(n - 1) % model + memory(n - 2) % model )) % model; memoryAraray[n] = ans; return ans; }在记忆化递归中，已经能够解决时间复杂度的问题了，但额外增加了空间，若在此优化空间复杂度使用动态规划即可解决。一般来说，只要递归能够解决的动态规划就一定能够解决，使用动态规划方法实现时间和空间的优化。代码如下：
public int fib(int n) { int a = 0, b = 1, sum; for(int i = 0; i < n; i++){ sum = (a + b) % 1000000007; a = b; b = sum; } return a; }