Introduction

Recursion 是一种解题方法：问题的解依赖于同一问题更小规模的解。

所有递归函数都包含两部分：

Base case（终止条件），否则递归会无限进行
把问题拆成更小的子问题并递归调用

最经典的例子是 Fibonacci 序列：

Base cases：fib(0) = 0 与 fib(1) = 1
Recurrence relation：fib(i) = fib(i-1) + fib(i-2)

def fib(n):
  if n <= 1:
    return n
  return fib(n - 1) + fib(n - 2)

很多面试相关算法都大量使用 recursion，例如 binary search、merge sort、tree traversal、DFS 等。本文聚焦那些使用 recursion 但不属于经典算法的题型。

Learning resources

面试时需要注意

一定要定义 base case，否则 recursion 不会结束。
Recursion 常用于 permutation，因为它能生成所有组合与 tree-based 问题。你需要掌握生成所有 permutations，以及如何处理重复值。
Recursion 隐式使用 stack，因此都可以改写成使用 stack 的迭代方式。注意 recursion 深度过深会 stack overflow（Python 默认 1000）。能指出这一点会加分。Recursion 不可能是 O(1) space，因为有 stack，除非语言支持 tail-call optimization (TCO)。
Base case 数量要足够。例如 Fibonacci 里调用 fib(n - 2)，说明要有两个 base cases。如果你的递归只调用 fn(n - 1)，则一个 base case 就够了。

Corner cases

n = 0
n = 1
确保 base cases 覆盖所有可能的递归调用范围

Techniques

Memoization

很多递归会重复计算。回到 Fibonacci：fib(5) 调 fib(4) 和 fib(3)，而 fib(4) 又调 fib(3) 和 fib(2)，fib(3) 被算了两次！如果把 fib(3) 的结果 memoize，再复用，可显著提升效率，时间复杂度可降为 O(n)。

Essential questions

该 topic 必练题。

Recommended practice questions

在掌握基础后推荐练习。

Recommended courses

Coding interview 的 Recursion cheatsheet

Introduction