算法（三）：递归与分治

• 递归是指函数自己调用自己的语法现象
• 一般递归用于将问题不断转化为规模更小的子问题，直到变为可以直接求解的最简单子问题。这也就是分治法的思想。
• 递归是许多算法和数据结构的基础。
  • 排序 中的快速排序、归并排序，双指针， 二分查找，动态规划 等算法本质上都是分治的思想。
  • 回溯法、dfs 一般借助递归来实现。
  • 树 的定义即是递归的。

递归是自顶向下的，思考逻辑比较自然直接，但有时递归层数太多会爆栈。 所以还需要掌握非递归的写法，也就是自底向上的递推写法。

1 基础

• 0050 Pow(x, n)
• 0078 子集
• 0779 第K个语法符号

2 进阶

• 0060 排列序列
• 0301 删除无效的括号
• 0372 超级次方
• 0390 消除游戏
• 0395 至少有 K 个重复字符的最长子串

3 挑战

• 0273 整数转换英文表示
• 1823 找出游戏的获胜者

4 树上递归