程序员必备的基本算法：递归详解( 三 ) 前言递归是一种非常重要的算法思想

文章插图
显然，「递推关系式」就是：
invertTree（root）= invertTree（root.left） + invertTree（root.right）;【程序员必备的基本算法：递归详解】于是，很容易可以得出以下代码：
//翻转一颗二叉树public TreeNode invertTree(TreeNode root) {if(root==null || (root.left ==null}//翻转左子树TreeNode left = invertTree(root.left);//翻转右子树TreeNode right= invertTree(root.right);}这里代码有个地方需要注意，翻转完一棵树的左右子树，还要交换它左右子树的引用位置。
root.left = right; root.right = left;因此， leetcode这个递归经典题目的「终极解决代码」如下：
class Solution {public TreeNode invertTree(TreeNode root) {if(root==null || (root.left ==null}//翻转左子树TreeNode left = invertTree(root.left);//翻转右子树TreeNode right= invertTree(root.right);//左右子树交换位置~root.left = right;root.right = left;return root;}}拿终极解决代码去leetcode提交一下，通过啦~
文章插图
递归存在的问题

递归调用层级太多，导致栈溢出问题
递归重复计算，导致效率低下

栈溢出问题

每一次函数调用在内存栈中分配空间，而每个进程的栈容量是有限的。
当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。
其实，我们在前面小节也讨论了，递归过程类似于出栈入栈，如果递归次数过多，栈的深度就需要越深，最后栈容量真的不够咯

「代码例子如下：」

/** * 递归栈溢出测试 */public class RecursionTest {public static void main(String[] args) {sum(50000);}private static int sum(int n) {if (n <= 1) {return 1;}return sum(n - 1) + n;}}

「运行结果:」
Exception in thread "main" java.lang.StackOverflowError at recursion.RecursionTest.sum(RecursionTest.java:13)怎么解决这个栈溢出问题？首先需要「优化一下你的递归」，真的需要递归调用这么多次嘛？如果真的需要，先稍微「调大JVM的栈空间内存」，如果还是不行，那就需要弃用递归，「优化为其他方案」咯~
重复计算，导致程序效率低下我们再来看一道经典的青蛙跳阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
绝大多数读者朋友，很容易就想到以下递归代码去解决：

class Solution {public int numWays(int n) {if (n == 0){return 1;}if(n <= 2){return n;}return numWays(n-1) + numWays(n-2);}}

但是呢，去leetcode提交一下，就有问题啦，超出时间限制了

文章插图
为什么超时了呢？递归耗时在哪里呢？先画出「递归树」看看：

文章插图

要计算原问题 f(10) ，就需要先计算出子问题 f(9) 和 f(8)
然后要计算 f(9) ，又要先算出子问题 f(8) 和 f(7) ，以此类推。
一直到 f(2) 和 f(1），递归树才终止。

我们先来看看这个递归的时间复杂度吧，「递归时间复杂度 = 解决一个子问题时间*子问题个数」