终于弄懂算法中递归的执行过程
终于弄懂算法中递归的执行过程
递归实现的原理：
一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：
- 运动开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；
- 每次执行递归调用之前，把递归函数的值参、局部变量的当前值以及调用后的返回地址压栈；
- 每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。
递归与栈的关系
其实，递归的过程，可以理解为出入栈的过程的，这个比喻呢，只是为了方便读者朋友更好理解递归哈。以上代码例子计算sum（n=3）的出入栈图如下：
为了更容易理解一些，我们来看一下 函数sum（n=5）的递归执行过程，如下：
- 计算sum（5）时，先sum（5）入栈，然后原问题sum（5）拆分为子问题sum（4），再入栈，直到终止条件sum（n=1）=1，就开始出栈。
- sum（1）出栈后，sum（2）开始出栈，接着sum（3）。
- 最后呢,sum（1）就是后进先出，sum（5）是先进后出，因此递归过程可以理解为栈出入过程。
实例分析
我对递归的理解是先往下一层层传递，当碰到终止条件的时候会反弹，最终会反弹到调用处。下面我们就以5个最常见的示例来分析下
1，阶乘
我们先来看一个最简单的递归调用-阶乘，代码如下
public int recursion(int n) {
if (n == 1)
return 1;
return n * recursion(n - 1);
}这个递归在熟悉不过了，第2-3行是终止条件，第4行是调用自己。我们就用n等于5的时候来画个图看一下递归究竟是怎么调用的：
这种递归还是很简单的，我们求f(5)的时候，只需要求出f(4)即可，如果求f(4)我们要求出f(3)……，一层一层的调用，当n=1的时候，我们直接返回1，然后再一层一层的返回，直到返回f(5)为止。
递归的目的是把一个大的问题细分为更小的子问题，我们只需要知道递归函数的功能即可，不要把递归一层一层的拆开来想，如果同时调用多次的话这样你很可能会陷入循环而出不来。比如上面的题中要求f(5)，我们只需要计算f(4)即可，即f(5)=5*f(4)；至于f(4)是怎么计算的，我们就不要管了。因为我们知道f(n)中的n可以代表任何正整数，我们只需要传入4就可以计算f(4)。
2、二叉树的遍历
再来看最后一个常见的示例就是二叉树的遍历，分为前序遍历、中序遍历、后序遍历，代码其实都差不多，这里只列出其中一个遍历。
前序遍历：
终止条件是node等于空，逻辑处理这块直接打印当前节点的值即可，递归调用是先打印左子树在打印右子树，我们来看下
public static void preOrder(TreeNode node) {
if (node == null)
return;
System.out.printf(node.val + "");
preOrder(node.left);
preOrder(node.right);
}3、翻转一棵二叉树
[1.定义函数功能]
函数功能（即这个递归原问题是），给出一颗树，然后翻转它。
[2.寻找递归终止条件]
这棵树什么时候不用翻转呢？当然是当前节点为null或者当前节点为叶子节点的时候啦。因此，加上终止条件就是：
//翻转一颗二叉树
public TreeNode invertTree(TreeNode root) {
if(root==null || (root.left ==null && root.right ==null)){
return root;
}
}[3.递推函数的等价关系式]
首先，你要翻转根节点为4的树，就需要翻转它的左子树（根节点为2）和右子树(根节点为7）。
然后呢，根节点为2的树，不是叶子节点，你需要继续翻转它的左子树（根节点为1）和右子树（根节点为3）。因为节点1和3都是叶子节点了，所以就返回啦。
同理，根节点为7的树，也不是叶子节点，你需要翻转它的左子树（根节点为6）和右子树（根节点为9）。因为节点6和9都是叶子节点了，所以也返回啦。
左子树（根节点为2）和右子树(根节点为7）都被翻转完后，这几个步骤就「归来」，即递归的过程，翻转树的任务就完成了。
显然，「递推关系式」就是：
invertTree（root）= invertTree（root.left） + invertTree（root.right）;于是，很容易可以得出以下代码：
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null || (root.left ==null && root.right ==null)){
return root;
}
//翻转左子树
TreeNode left = invertTree(root.left);
//翻转右子树
TreeNode right= invertTree(root.right);
//左右子树交换位置~
root.left = right;
root.right = left;
return root;
}
}递归存在的问题
- 递归调用层级太多，导致栈溢出问题
- 递归重复计算，导致效率低下
我们再来看一道经典的青蛙跳阶问题：
一只青蛙一次可以跳上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），递归树才终止。
我们先来看看这个递归的时间复杂度吧，递归时间复杂度 = 解决一个子问题时间*子问题个数
- 一个子问题时间 = f（n-1）+f（n-2），也就是一个加法的操作，所以复杂度是 「O(1)」；
- 问题个数 = 递归树节点的总数，递归树的总结点 = 2^n-1，所以是复杂度「O(2^n)」。
因此，青蛙跳阶，递归解法的时间复杂度 = O(1) * O(2^n) = O(2^n)，就是指数级别的，爆炸增长的，如果n比较大的话，超时很正常的了。
回过头来，你仔细观察这颗递归树，你会发现存在大量重复计算，比如f（8）被计算了两次，f（7）被重复计算了3次...所以这个递归算法低效的原因，就是存在大量的重复计算！
怎么解决这个问题呢？
既然存在大量重复计算，那么我们可以先把计算好的答案存下来，造一个备忘录，等到下次需要的话，先去「备忘录」查一下，如果有，就直接取就好了，备忘录没有才再计算，那就可以省去重新重复计算的耗时啦！这就是带备忘录的解法.
一般使用一个数组或者一个哈希map充当这个「备忘录」。
假设f(10)求解加上「备忘录」，我们再来画一下递归树：
「第一步」，f（10）= f(9) + f(8)，f(9) 和f（8）都需要计算出来，然后再加到备忘录中，如下：
「第二步」 , f(9) = f（8）+ f（7），f（8）= f（7）+ f(6), 因为 f(8) 已经在备忘录中啦，所以可以省掉，f(7),f（6）都需要计算出来，加到备忘录中~
「第三步」 ,f(8) = f（7）+ f(6),发现f(8)，f(7),f（6）全部都在备忘录上了，所以都可以剪掉。
所以呢，用了备忘录递归算法，递归树变成光秃秃的树干，如下：
带「备忘录」的递归算法，子问题个数=树节点数=n，解决一个子问题还是O(1),所以「带「备忘录」的递归算法的时间复杂度是O(n)」。接下来呢，我们用带「备忘录」的递归算法去撸代码，解决这个青蛙跳阶问题的超时问题，代码如下：
public class Solution {
//使用哈希map，充当备忘录的作用
Map<Integer, Integer> tempMap = new HashMap();
public int numWays(int n) {
// n = 0 也算1种
if (n == 0) {
return 1;
}
if (n <= 2) {
return n;
}
//先判断有没计算过，即看看备忘录有没有
if (tempMap.containsKey(n)) {
//备忘录有，即计算过，直接返回
return tempMap.get(n);
} else {
// 备忘录没有，即没有计算过，执行递归计算,并且把结果保存到备忘录map中，对1000000007取余（这个是leetcode题目规定的）
tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
return tempMap.get(n);
}
}
}