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
Every recursive function rests on the same two pillars — a base case that stops the descent and a recursive case that shrinks the problem toward it — and these terms are the vocabulary the rest of the sheet builds on. Knowing how frames pile onto the call stack during the winding phase and unwind on return is what separates a working solution from a stack overflow, so it pays to internalize this template before reaching for the fancier patterns.
| 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 |