递归最大的问题就是要防止栈溢出以及死循环。为何递归容易造成栈溢出呢？我们回想下之前说过的栈数据结构，不清楚的朋友可以翻阅历史文章。函数调用会使用栈来保存临时变量，每次调用一个函数都会把临时变量封装成栈帧压入线程对应的栈中，等方法结束返回时，才出栈。如果递归的数据规模比较大，调用层次很深就会导致一直压入栈，而栈的大小通常不会很大就会导致堆栈溢出的情况。
Exception in thread "main" java.lang.StackOverflowError如何防止呢？
我们只能在代码里面限制最大深度，直接返回错误，使用一个全局变量表示递归的深度，每次执行都 + 1，当超过指定阈值还没有结束的时候直接返回错误。
警惕重复计算青蛙跳台阶的问题就有重复计算的问题，我们试着把递归过程分解下，想要计算 f(5)，需要先计算 f(4) 和 f(3)，而计算 f(4) 还需要计算 f(3)，因此，f(3) 就被计算了很多次，这就是重复计算问题。为了避免重复计算，我们可以通过一个数据结构（比如 HashMap）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了。
public int f(int n) { if (n == 1) return 1; if (n == 2) return 2; // hasSolvedList 可以理解成一个 Map，key 是 n，value 是 f(n) if (hasSolvedMap.containsKey(n)) { return hasSovledMap.get(n); } int ret = f(n-1) + f(n-2); hasSovledMap.put(n, ret); return ret; }递归的空间复杂度因为每次调用都会在栈上保存一次临时变量，所以它的空间复杂度就是 O(N),而不是 O(1)。
如何将递归转换成非递归代码递归有利有弊，递归写起来很简洁，而不好的地方就是空间复杂度是 O(n)，有堆栈溢出风险，存在重复计算。要根具体情况来选择是否需要递归。
还是军训排队报数的例子，如何变成非递归。
f(n) = f(n-1) +1;
public int f(n) { int r = 1; for(int i = 2; i <= n; i++) { r += 1; } return r; }对于台阶问题也是可以改成循环实现。
public int f(int n) { if (n == 1) return 1; if (n == 2) return 2; int ret = 0; int pre = 2; int prepre = 1; for (int i = 3; i <= n; ++i) { ret = pre + prepre; prepre = pre; pre = ret; } return ret; } 寻找最佳推荐人现在递归说完了，我们如何解答开篇的问题：根据士兵 id 找到最佳推荐人？
public int findRootReferId(int soldierId) { Integer referId = "select reference_id from [table] where soldier_id = soldierId"; if (referId == null) return soldierId; return findRootReferId(referId); }递归是一种非常高效、简洁的编码技巧。只要是满足“三个条件”的问题就可以通过递归代码来解决。
不过递归代码也比较难写、难理解。编写递归代码的关键就是不要把自己绕进去，正确姿势是写出递推公式，找出终止条件，然后再翻译成递归代码。
递归代码虽然简洁高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所以，在编写递归代码的时候，一定要控制好这些副作用。
推荐阅读1.
2.
3.
4.
5.
6.
7.
8.
9.
原创不易，觉得有用希望随手「在看」「收藏」「转发」三连。