什么是递归？

程序反复调用自身即为递归。

举例：

1
2
3
4
const factorial = (n:number) => {
	if(n<=1) return 1;
	return n * factorial(n - 1); 
}

我掉入的纠结点误区

总是在纠结这一层函数在干嘛，它调用自身函数后，又做了什么。
这其实掉入了思维误区，现在就想着这每一层功能都是一样的，专注点在一级递归的解决过程就行了。

递归题套路公式

1、确定函数返回值

2、基线条件（确定终止条件，不然会陷入死循环）

3、确定要递归的元素

举例套公式分析（翻转二叉树）

分析：

1、确定函数的返回值：返回二叉树

2、确定终止条件：二叉树左右子树都遍历完，二叉树的value值为空，结束

3、确定要递归的元素：左子树和右子树要递归

1
2
3
4
5
6
7
8
9
10
// 1、返回值: TreeNode 或 null
const invertTree = (root: TreeNode | null): TreeNode | null => {
  // 2、终止条件: root为空
  if (!root) return null;
  return {
    val: root.val,
    left: invertTree(root.right), // 3、要递归的元素：root.right
    right: invertTree(root.left), // 3、要递归的元素：root.left
  };
};

更多递归例题：(斐波那契数列、翻转二叉树、判断是否为对称二叉树、合并二叉树等等)

https://github.com/Sugar-MM/AlgorithmPractice/tree/main/src/recursion