Recursion is a powerful programming technique where a function calls itself to solve smaller instances of the same problem. Mastery requires understanding recursion types (linear vs. branching, head vs. tail), optimization strategies (tail-call optimization, memoization, trampolining), complexity analysis (recursion trees, master theorem), and practical patterns (divide and conquer, backtracking, tree traversals, converting recursion to iteration). This cheat sheet covers all major recursion patterns from fundamentals through advanced topics.
What This Cheat Sheet Covers
This topic spans 14 focused tables and 228 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Table 1: Recursion Fundamentals β Structure and Terminology
| Concept | Syntax / Formula | Notes |
|---|---|---|
if n == 0: return 1 | β’ Condition that stops recursion β’ every recursive function must have one | |
return n * factorial(n-1) | β’ Reduces problem toward base case β’ must make progress | |
[return addr, local vars, params] | β’ Each call pushes a new frame β’ popped on return | |
| Python default: 1000 frames | β’ sys.setrecursionlimit(n) to raiseβ’ deep recursion β stack overflow | |
| Recurses on structural subset of input | β’ Input is a list/tree β’ recursive call on cdr or child nodes |