Rt. 可能大家都或多或少的听见过类似的话或者建议：
尽量少使用递归操作，甚至干脆就不要使用递归操作。
但大家在听到这句话的时候，是否会产生过疑问，为什么不建议使用递归操作呢？
现在，我们就一起聊聊这个话题，看看递归到底会产生什么样的问题。
首先，大家思考一道算法题：如何实现二叉树的中序遍历？
对于树的遍历，无论是前序、中序还是后序遍历，大家可能下意识的就会想到使用递归操作，为什么呢？因为递归操作实现起来“简单”啊！
下面为实现二叉树中序遍历的 Java 递归实现，代码来自于 Gitee 的「myleetcode」项目：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
helper(root, ans);
return ans;
}
private void helper(TreeNode root, List<Integer> res) {
if (root != null) {
if (root.left != null) {
helper(root.left, res);
}
res.add(root.val);
if (root.right != null) {
helper(root.right, res);
}
}
}
下面为实现二叉树中序遍历的 Java 迭代实现，代码同样来自于 Gitee 的「myleetcode」项目：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
观察上述两部分代码，相比于迭代，在使用递归的时候，我们会在函数的某一部分，重复的调用某个函数自身，直到触发终止条件时，递归才会停止，进而函数才会执行完毕。说到这里，我们就发现了递归可能会产生问题的第一个地方：
- 如果终止条件有问题，那么递归将无法停止。
那么，我们进一步分析，如果递归无法停止，会出现什么问题呢？
- 如果递归无法停止，函数会不断的调用自身，从而无法执行后序的流程。
到这里，我们已经从逻辑上分析了递归可能会产生的问题。
接下来，我们再从 JVM 的层面上，分析递归可能会产生的问题。
我们知道，Java 源代码需要编译成字节码文件，由 JVM 解释执行，为了能高效地管理程序方法调用，有条不紊地进行嵌套的方法调用和方法返回，JVM 维护了一个栈结构，称为虚拟机方法栈（如果调用的是 Native 方法，则为本地方法栈）。
栈里面存放的一个个实体称为栈帧，每个栈帧都包括了局部变量表、操作数栈、动态连接、方法返回地址和一些额外的附加信息。在 JVM 中，方法调用的过程大致为：
- 除非被调用的方法是类方法，否则在每一次方法调用指令之前，JVM 会先把方法被调用的对象引用压入操作数栈中，除了对象的引用之外，JVM 还会把方法的参数依次压入操作数栈；
- 在执行方法调用指令时，JVM 会将函数参数和对象引用依次从操作数栈弹出，并新建一个栈帧，把对象引用和函数参数分别放入新栈帧的局部变量表；
- JVM 把新栈帧压入虚拟机方法栈，并把 PC（程序计数器）指向函数的第一条待执行的指令。
因此，我们总是说，每个方法的执行过程，都是一个栈帧从入栈到出栈的过程。这意味着，在执行递归操作的时候，如果终止条件有问题，无法终止递归，则会出现：
- 虚拟机方法栈只入栈不出栈
进而，当栈中所有栈帧的大小总和大于-Xss设置的值时，则会出现栈溢出，即：
- 抛出
StackOverflowError异常
此外，函数的执行是有一定开销的，例如每次都要保存局部变量、参数、调用函数地址、返回值等，而递归的开销还要在此基础上乘以迭代次数，这自然会影响到函数的执行效率。
但对于某些问题，如上面我们考虑的二叉树的中序遍历，在条件允许的情况下，我们还是倾向于使用递归实现的，因为相对来说，递归的实现更简单，也更容易理解。
说的这里，我们不妨再来聊聊如何优化递归，其方法主要有两个，分别为：
- 限制递归次数
- 使用尾递归形式
对于“限制递归次数”来说，就是在调用函数的时候，同时传入一个数字 N 作为递归的次数；
对于“使用尾递归形式”来说，则是尽量将递归中对函数本身的调用下移，最好是函数的最后一行代码。
聊到这里，本篇文章就结束了，希望对大家有所帮助。如果大家对递归有其他的理解，请积极留言，我们一起探讨！
转载：https://blog.csdn.net/qq_35246620/article/details/104855300