递归的概念

递归就是一个函数调用他本身，与普通函数调用类似，例如函数A调用另一个函数B，就是函数A调用函数B时程序中断,指令跳转到函数B执行，函数B执行完之后再返回到函数A的中断处，继续下一条语句执行。
编写递归3大要素：

1. 想清楚这个函数实现什么功能，设置入参和返回值
2. 设置退出条件（需要退出递归）
3. 推导递推公式，没有递推就没有递归

示例

1.常见的阶乘问题
f(n) = n!

int fac(int n) {
  if(n == 1) {
    return 1;
  }
  return n * fac(n-1);
}

递归示例：

函数调用栈：
每执行一次函数，就入栈一次，直到递归到底，碰到退出条件，就执行最后一个函数，弹出栈，然后依次运行未执行完的函数，执行完就弹出函数调用栈，最后返回到main函数，执行完毕弹出。

2.二叉树的遍历
二叉树的数据结构天然具有递归性，所以可以直接用递归来遍历二叉树
前序遍历：

public void traverse(TreeNode root) {
    if( root == null){
      return;
    }
    System.out.println(root.val);
    traverse(root.left);
    traverse(root.right);
  }

中序遍历：

public void traverse(TreeNode root) {
    if( root == null){
      return;
    }
    traverse(root.left);
    System.out.println(root.val);
    traverse(root.right);
  }

后序遍历：

public void traverse(TreeNode root) {
    if( root == null){
      return;
    }
    traverse(root.left);
    traverse(root.right);
    System.out.println(root.val);
  }

通过前序、中序、后序遍历可以发现处理逻辑在递归哪里很有讲究，下面我们研究下：
通过先前函数调用栈的分析，可知在调用一个函数前，必定执行调用函数语句之前的语句逻辑，执行完之后才继续执行未完成的逻辑。
前序遍历：
在调用下一个节点遍历函数时，就先执行输出当前节点的值，所以根节点的数据总是在最前面输出的；
中序遍历：
在调用下一个右节点遍历函数时，执行输出当前节点的值，所以根节点数据总是在左节点之后输出；
后序遍历：
在递归函数后执行，所以函数递归完了才处理这部分逻辑，跟节点总是最后输出。

总结

碰到递归问题，不能陷入到递归调用栈中去，人的脑子不比计算机，没那么大的内存容量。我们首先要相信递归函数的能力，能处理好它做的事情，比如二叉树遍历函数void traverse(TreeNode root)，我们相信给遍历函数一个根节点，它就能遍历给定根节点的树。
递归使用数学归纳法思想：
1、设置边界条件
2、推导递推公式
3、假设n=m时成立，则n=m+1也成立

递归的理解