https://juejin.im/post/6844904008595816462
简单地说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫递归。
进一步剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决， 子问题再拆解成子子问题，...，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,....,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。
所以递归的本质是能把问题拆分成具有相同解决思路的子问题，。。。直到最后被拆解的子问题再也不能拆分，解决了最小粒度可求解的子问题后，在「归」的过程中自然顺其自然地解决了最开始的问题
一个问题可以分解成具有相同解决思路的子问题，子子问题，换句话说这些问题都能调用同一个函数
经过层层分解的子问题最后一定是有一个不能再分解的固定值的（即终止条件）,如果没有的话,就无穷无尽地分解子问题了，问题显然是无解的。
用实例来思考解决问题的思路
阶乘实例来演示递归解决问题的思路
阶乘n!
- 定义函数，明确功能
函数的功能是求 n 的阶乘
- 以 f(n) 来表示 问题与子问题的关系
描述关系，可以运用 运算关系 来组成 n 和 n-1(大小问题函数) 等...的关系。
可自上而下
f(n) = {
1, n = 1;
n*f(n-1)
}
- 将上述递推公式 转换为代码
/**
* 求 n 的阶乘
*/
public int factorial(int n) {
// 第二步的临界条件
if (n < =1) {
return 1;
}
// 第二步的递推公式
return n * factorial(n-1)
}- 求时间复杂度 由于 f(n) = n f(n-1) = n (n-1) .... f(1),总共作了 n 次乘法，所以时间复杂度为 n。
一只青蛙可以一次跳 1 级台阶或者一次跳 2 级台阶。问要跳上第 n 级台阶有多少种跳法？
f(n) = {
1,n=1
2,n=2
f(n-1) + f(n-2)
}可以优化为 迭代非递归
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public TreeNode invertTree(TreeNode root) {
}时间复杂度是 O(n)
空间复杂度为O(logn),