Coding interview 的 Recursion cheatsheet

Introduction

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

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

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

最经典的例子是 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

• Readings
  • Recursion, University of Utah
• Videos
  • Tail Recursion, University of Washington

面试时需要注意

• 一定要定义 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 必练题。

• Generate Parentheses
• Combinations
• Subsets

Recommended practice questions

在掌握基础后推荐练习。

• Letter Combinations of a Phone Number
• Subsets II
• Permutations
• Sudoku Solver
• Strobogrammatic Number II (LeetCode Premium)

Recommended courses