当我们使用递归来解决一个问题的时候，容易产生重复去算同一个子问题，这个时候我们要考虑状态保存以防止重复计算。例如我随便举一个之前举过的问题
问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？
这个问题用递归很好解决。假设 f(n) 表示n级台阶的总跳数法，则有
f(n) = f(n-1) + f(n - 2)。
递归的结束条件是当0 <= n <= 2时, f(n) = n。因此我们可以很容易写出递归的代码
public int f(int n) { if (n <= 2) { return n; } else { return f(n - 1) + f(n - 2); } }不过对于可以使用递归解决的问题，我们一定要考虑是否有很多重复计算。显然对于 f(n) = f(n-1) + f(n-2) 的递归，是有很多重复计算的。如
就有很多重复计算了。这个时候我们要考虑状态保存。例如用hashMap来进行保存，当然用一个数组也是可以的，这个时候就像我们上面说的巧用数组下标了。可以当arr[n] = 0时，表示n还没计算过，当arr[n] != 0时，表示f(n)已经计算过，这时就可以把计算过的值直接返回回去了。因此我们考虑用状态保存的做法代码如下：
//数组的大小根据具体情况来，由于int数组元素的的默认值是0 //因此我们不用初始化 int[] arr = new int[1000]; public int f(int n) { if (n <= 2) { return n; } else { if (arr[n] != 0) { return arr[n];//已经计算过，直接返回 } else { arr[n] = f(n-1) + f(n-2); return arr[n]; } } }这样，可以极大着提高算法的效率。也有人把这种状态保存称之为备忘录法。
(2).考虑自底向上
对于递归的问题，我们一般都是从上往下递归的，直到递归到最底，再一层一层着把值返回。
不过，有时候当n比较大的时候，例如当 n = 10000时，那么必须要往下递归10000层直到 n <=2 才将结果慢慢返回，如果n太大的话，可能栈空间会不够用。
对于这种情况，其实我们是可以考虑自底向上的做法的。例如我知道
f(1) = 1;
f(2) = 2;
那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此，我们可以考虑使用自底向上的方法来做。
代码如下：
public int f(int n) { if(n <= 2) return n; int f1 = 1; int f2 = 2; int sum = 0; for (int i = 3; i <= n; i++) { sum = f1 + f2; f1 = f2; f2 = sum; } return sum; }我们也把这种自底向上的做法称之为递推。
总结一下
当你在使用递归解决问题的时候，要考虑以下两个问题
(1). 是否有状态重复计算的，可不可以使用备忘录法来优化。
(2). 是否可以采取递推的方法来自底向上做，减少一味递归的开销。
最后推广下我的公众号：苦逼的码农，文章都会首发于我的公众号，期待各路英雄的关注交流。