Recursion Patterns

1. Tree Recursion Patterns

Pattern	Structure	Complexity	Application
Single Branch	One recursive call per invocation	`O(n)` linear	Linked list traversal, linear search
Binary Tree	Two recursive calls (left, right)	`O(2^h)` exponential	Binary tree traversal, Fibonacci naive
N-ary Tree	N recursive calls for N children	`O(N^h)`	Directory traversal, game trees
Pruned Tree	Conditional recursion with early exit	Better than worst case	Backtracking, search with constraints

Example: Binary tree recursion

// Preorder traversal
function preorder(root) {
    if (!root) return;
    
    console.log(root.val);  // Process root
    preorder(root.left);    // Recurse left
    preorder(root.right);   // Recurse right
}

// Inorder traversal
function inorder(root) {
    if (!root) return;
    
    inorder(root.left);
    console.log(root.val);
    inorder(root.right);
}

// Postorder traversal
function postorder(root) {
    if (!root) return;
    
    postorder(root.left);
    postorder(root.right);
    console.log(root.val);
}

// Time: O(n), Space: O(h) recursion stack

Example: N-ary tree recursion

function traverseNary(root) {
    if (!root) return;
    
    // Process current node
    console.log(root.val);
    
    // Recurse on all children
    for (const child of root.children) {
        traverseNary(child);
    }
}

// Count nodes in N-ary tree
function countNodes(root) {
    if (!root) return 0;
    
    let count = 1; // Current node
    
    for (const child of root.children) {
        count += countNodes(child);
    }
    
    return count;
}

// Time: O(n), Space: O(h)

Example: Tree recursion with return value

// Find maximum value in binary tree
function findMax(root) {
    if (!root) return -Infinity;
    
    const leftMax = findMax(root.left);
    const rightMax = findMax(root.right);
    
    return Math.max(root.val, leftMax, rightMax);
}

// Check if tree is symmetric
function isSymmetric(root) {
    function isMirror(left, right) {
        if (!left && !right) return true;
        if (!left || !right) return false;
        
        return left.val === right.val &&
               isMirror(left.left, right.right) &&
               isMirror(left.right, right.left);
    }
    
    return !root || isMirror(root.left, root.right);
}

// Path sum exists
function hasPathSum(root, targetSum) {
    if (!root) return false;
    
    // Leaf node
    if (!root.left && !root.right) {
        return root.val === targetSum;
    }
    
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
}

2. Tail Recursion Optimization

Concept	Definition	Benefit	Limitation
Tail Call	Recursive call is last operation	Can reuse stack frame	No pending operations after recursion
TCO (Tail Call Optimization)	Compiler optimization to O(1) space	Converts recursion to iteration	Not guaranteed in JavaScript
Accumulator Pattern	Pass result as parameter	Enables tail recursion	Requires function redesign
Manual Conversion	Rewrite as while loop	Guaranteed O(1) space	More verbose code

Example: Non-tail recursive factorial

function factorial(n) {
    if (n <= 1) return 1;
    
    // NOT tail recursive
    // Pending operation: multiply result by n
    return n * factorial(n - 1);
}

// Stack frames:
// factorial(5)
//   5 * factorial(4)
//     4 * factorial(3)
//       3 * factorial(2)
//         2 * factorial(1)
//           return 1
//         return 2 * 1 = 2
//       return 3 * 2 = 6
//     return 4 * 6 = 24
//   return 5 * 24 = 120

// Space: O(n) stack frames

Example: Tail recursive factorial

function factorialTail(n, acc = 1) {
    if (n <= 1) return acc;
    
    // Tail recursive
    // No pending operations after recursion
    return factorialTail(n - 1, n * acc);
}

// With TCO optimization:
// factorialTail(5, 1)
// factorialTail(4, 5)   // reuse frame
// factorialTail(3, 20)  // reuse frame
// factorialTail(2, 60)  // reuse frame
// factorialTail(1, 120) // reuse frame
// return 120

// Space: O(1) with TCO
// Without TCO: still O(n) in JavaScript

Example: Converting to iterative (guaranteed O(1) space)

// Tail recursive Fibonacci
function fibTail(n, a = 0, b = 1) {
    if (n === 0) return a;
    if (n === 1) return b;
    return fibTail(n - 1, b, a + b);
}

// Iterative version (manual tail call elimination)
function fibIterative(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    let a = 0, b = 1;
    
    for (let i = 2; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    
    return b;
}

// Both O(n) time, iterative guaranteed O(1) space
// fibTail depends on TCO support

// Sum of array - tail recursive
function sumTail(arr, index = 0, acc = 0) {
    if (index === arr.length) return acc;
    return sumTail(arr, index + 1, acc + arr[index]);
}

// Iterative equivalent
function sumIterative(arr) {
    let sum = 0;
    for (const num of arr) {
        sum += num;
    }
    return sum;
}

3. Recursion Tree Complexity Analysis

Example	Recursion Tree	Work Per Level	Total Complexity
Linear (Factorial)	Single branch, depth n	`O(1)`	`O(n)`
Binary (Fibonacci naive)	2 children, depth n	`O(2^level)`	`O(2^n)`
Divide & Conquer (Merge Sort)	2 children, depth log n	`O(n)`	`O(n log n)`
Master Theorem	T(n) = aT(n/b) + f(n)	Depends on f(n) vs n^(log_b a)	Three cases determine result

Example: Fibonacci recursion tree analysis

function fib(n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

/*
Recursion tree for fib(5):

                    fib(5)
                   /      \
              fib(4)      fib(3)
             /     \      /     \
        fib(3)  fib(2) fib(2) fib(1)
        /   \    /  \   /  \
    fib(2) fib(1) ...  ...

Level 0: 1 node  = 2^0
Level 1: 2 nodes = 2^1
Level 2: 4 nodes = 2^2
...
Level k: 2^k nodes (approximately)

Depth ≈ n
Total nodes ≈ 2^n
Time: O(2^n), Space: O(n) stack depth
*/

// Each fib(k) computed multiple times!
// fib(3) computed twice, fib(2) three times, etc.
// Overlapping subproblems -> use memoization!

Example: Master Theorem applications

// Binary Search: T(n) = T(n/2) + O(1)
// a=1, b=2, f(n)=O(1)
// log_b(a) = log_2(1) = 0
// f(n) = O(n^0) = O(1)
// Case 2: f(n) = Θ(n^log_b(a))
// Result: O(log n)

// Merge Sort: T(n) = 2T(n/2) + O(n)
// a=2, b=2, f(n)=O(n)
// log_b(a) = log_2(2) = 1
// f(n) = O(n^1) = O(n)
// Case 2: f(n) = Θ(n^log_b(a))
// Result: O(n log n)

// Karatsuba: T(n) = 3T(n/2) + O(n)
// a=3, b=2, f(n)=O(n)
// log_b(a) = log_2(3) ≈ 1.585
// f(n) = O(n^1) < O(n^1.585)
// Case 1: f(n) = O(n^c) where c < log_b(a)
// Result: O(n^log_2(3)) ≈ O(n^1.585)

// Strassen Matrix: T(n) = 7T(n/2) + O(n^2)
// a=7, b=2, f(n)=O(n^2)
// log_b(a) = log_2(7) ≈ 2.807
// f(n) = O(n^2) < O(n^2.807)
// Case 1: Result: O(n^log_2(7)) ≈ O(n^2.807)

4. Memoization (Top-Down DP)

Concept	Mechanism	Benefit	Trade-off
Caching Results	Store computed values in map/array	Avoid redundant computations	Extra space for cache
Top-Down Approach	Start from problem, recurse to base	Natural recursive thinking	Recursion stack overhead
Lazy Computation	Only compute needed subproblems	May compute fewer states than bottom-up	Function call overhead
When to Use	Overlapping subproblems exist	Convert O(2^n) to O(n) or O(n²)	Need to identify subproblem structure

Example: Fibonacci with memoization

function fibMemo(n, memo = {}) {
    // Check cache
    if (n in memo) return memo[n];
    
    // Base cases
    if (n <= 1) return n;
    
    // Compute and cache
    memo[n] = fibMemo(n - 1, memo) + 
              fibMemo(n - 2, memo);
    
    return memo[n];
}

// Alternatively with array
function fibMemoArray(n) {
    const memo = Array(n + 1).fill(-1);
    
    function helper(n) {
        if (memo[n] !== -1) return memo[n];
        if (n <= 1) return n;
        
        memo[n] = helper(n - 1) + helper(n - 2);
        return memo[n];
    }
    
    return helper(n);
}

// Time: O(n), Space: O(n)
// Each subproblem computed once!

Example: Climbing stairs memoized

function climbStairs(n) {
    const memo = {};
    
    function climb(n) {
        if (n in memo) return memo[n];
        
        if (n <= 2) return n;
        
        memo[n] = climb(n - 1) + climb(n - 2);
        return memo[n];
    }
    
    return climb(n);
}

// Time: O(n), Space: O(n)
// Without memoization: O(2^n)

// Can take 1 or 2 steps at a time
// How many ways to reach step n?
// climb(n) = climb(n-1) + climb(n-2)

Example: Longest increasing subsequence (LIS) memoized

function lengthOfLIS(nums) {
    const memo = {};
    
    function lis(index, prev) {
        const key = `${index},${prev}`;
        if (key in memo) return memo[key];
        
        if (index === nums.length) return 0;
        
        // Option 1: Skip current element
        let skip = lis(index + 1, prev);
        
        // Option 2: Take current if valid
        let take = 0;
        if (prev === -1 || nums[index] > nums[prev]) {
            take = 1 + lis(index + 1, index);
        }
        
        memo[key] = Math.max(skip, take);
        return memo[key];
    }
    
    return lis(0, -1);
}

// [10,9,2,5,3,7,101,18] -> 4 ([2,3,7,101])
// Time: O(n²), Space: O(n²)

// Alternative: O(n) space with index-only memoization
function lengthOfLISOptimized(nums) {
    const memo = Array(nums.length).fill(-1);
    
    function lis(index) {
        if (memo[index] !== -1) return memo[index];
        
        let maxLen = 1;
        for (let j = 0; j < index; j++) {
            if (nums[j] < nums[index]) {
                maxLen = Math.max(maxLen, 1 + lis(j));
            }
        }
        
        memo[index] = maxLen;
        return maxLen;
    }
    
    let result = 0;
    for (let i = 0; i < nums.length; i++) {
        result = Math.max(result, lis(i));
    }
    
    return result;
}

5. Recursive Data Structures

Structure	Definition	Operations	Complexity
Linked List	Node + pointer to next node	Traverse, insert, delete recursively	O(n) time, O(n) space for recursion
Binary Tree	Node + left/right child pointers	All tree operations naturally recursive	O(n) time, O(h) space
Trie	Node + map of children	Search, insert, delete with recursion	O(L) where L = word length
Graph	Nodes + edges (adjacency list/matrix)	DFS naturally recursive	O(V + E)

Example: Recursive linked list operations

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

// Recursive traversal
function printList(head) {
    if (!head) return;
    console.log(head.val);
    printList(head.next);
}

// Recursive reverse
function reverseList(head) {
    if (!head || !head.next) return head;
    
    const newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    
    return newHead;
}

// Recursive search
function search(head, target) {
    if (!head) return false;
    if (head.val === target) return true;
    return search(head.next, target);
}

// Recursive insert at end
function insertEnd(head, val) {
    if (!head) return new ListNode(val);
    
    head.next = insertEnd(head.next, val);
    return head;
}

Example: Recursive tree construction

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// Build tree from inorder and preorder
function buildTree(preorder, inorder) {
    if (preorder.length === 0) return null;
    
    const rootVal = preorder[0];
    const root = new TreeNode(rootVal);
    
    const mid = inorder.indexOf(rootVal);
    
    root.left = buildTree(
        preorder.slice(1, mid + 1),
        inorder.slice(0, mid)
    );
    
    root.right = buildTree(
        preorder.slice(mid + 1),
        inorder.slice(mid + 1)
    );
    
    return root;
}

// Serialize tree
function serialize(root) {
    if (!root) return 'null';
    
    return root.val + ',' + 
           serialize(root.left) + ',' +
           serialize(root.right);
}

// Deserialize tree
function deserialize(data) {
    const values = data.split(',');
    let index = 0;
    
    function build() {
        if (values[index] === 'null') {
            index++;
            return null;
        }
        
        const node = new TreeNode(parseInt(values[index]));
        index++;
        node.left = build();
        node.right = build();
        
        return node;
    }
    
    return build();
}

6. Mutual Recursion Patterns

Pattern	Description	Example	Use Case
Two Functions	Function A calls B, B calls A	Even/odd checker, state machines	Alternating states
Multiple Functions	Cycle of 3+ functions	Parsing, expression evaluation	Complex state transitions
Base Cases	Each function needs termination	Critical for avoiding infinite loops	Careful design required
Conversion	Can convert to single function with state	Add parameter to track which "phase"	May simplify or complicate

Example: Even/odd mutual recursion

function isEven(n) {
    if (n === 0) return true;
    return isOdd(n - 1);
}

function isOdd(n) {
    if (n === 0) return false;
    return isEven(n - 1);
}

// isEven(4) -> isOdd(3) -> isEven(2) -> isOdd(1) -> isEven(0) -> true
// Demonstrates mutual recursion, though inefficient
// Better: return n % 2 === 0

Example: Expression parser mutual recursion

// Grammar:
// expr   -> term (('+' | '-') term)*
// term   -> factor (('*' | '/') factor)*
// factor -> number | '(' expr ')'

class Parser {
    constructor(tokens) {
        this.tokens = tokens;
        this.pos = 0;
    }
    
    parseExpr() {
        let result = this.parseTerm();
        
        while (this.pos < this.tokens.length &&
               (this.tokens[this.pos] === '+' || 
                this.tokens[this.pos] === '-')) {
            const op = this.tokens[this.pos++];
            const right = this.parseTerm();
            result = op === '+' ? result + right : result - right;
        }
        
        return result;
    }
    
    parseTerm() {
        let result = this.parseFactor();
        
        while (this.pos < this.tokens.length &&
               (this.tokens[this.pos] === '*' || 
                this.tokens[this.pos] === '/')) {
            const op = this.tokens[this.pos++];
            const right = this.parseFactor();
            result = op === '*' ? result * right : result / right;
        }
        
        return result;
    }
    
    parseFactor() {
        if (this.tokens[this.pos] === '(') {
            this.pos++; // Skip '('
            const result = this.parseExpr(); // Mutual recursion!
            this.pos++; // Skip ')'
            return result;
        }
        
        return parseInt(this.tokens[this.pos++]);
    }
}

// const parser = new Parser(['(', '2', '+', '3', ')', '*', '4']);
// parser.parseExpr() -> 20
// parseExpr calls parseTerm, parseTerm calls parseFactor,
// parseFactor calls parseExpr for nested expressions

Example: State machine mutual recursion

// Simple state machine: accepting strings with alternating a's and b's
function stateA(str, index) {
    if (index === str.length) return true; // Accept
    
    if (str[index] === 'a') {
        return stateB(str, index + 1); // Transition to B
    }
    
    return false; // Reject
}

function stateB(str, index) {
    if (index === str.length) return false; // Reject (must end in A)
    
    if (str[index] === 'b') {
        return stateA(str, index + 1); // Transition to A
    }
    
    return false; // Reject
}

function accepts(str) {
    if (str.length === 0) return false;
    return stateA(str, 0);
}

// accepts("ab") -> true
// accepts("abab") -> true
// accepts("aba") -> false
// accepts("abba") -> false

// Mutual recursion models state transitions

Recursion Patterns Summary

Tree Recursion: Binary/N-ary recursive calls, exponential growth without optimization
Tail Recursion: Last operation is recursive call, enables O(1) space with TCO
Recursion Tree Analysis: Visualize calls, count nodes per level, apply Master Theorem
Memoization: Cache results to convert O(2^n) to O(n) or O(n²)
Recursive Structures: Linked lists, trees, graphs naturally recursive
Mutual Recursion: Functions call each other, useful for state machines and parsers

Note: Memoization is critical for recursive problems with overlapping subproblems. Fibonacci naive: O(2^n), with memoization: O(n). Tail recursion optimization converts recursion to iteration internally, achieving O(1) space, but JavaScript engines may not guarantee TCO. When in doubt, manually convert to iteration.

Warning: Deep recursion can cause stack overflow. JavaScript typically allows ~10,000-50,000 frames. For very deep recursion, use iteration or trampolining. Memoization requires extra space - be mindful of memory constraints. In mutual recursion, ensure all functions have proper base cases to avoid infinite loops.

Related Cheat Sheets

Algorithm Patterns