Recursion Pattern

What is Recursion?

Recursion is when a function calls itself to solve smaller instances of the same problem. Every recursive solution has a base case (termination) and a recursive case (breakdown).

Quick Recognition: Problems that can be broken into smaller self-similar subproblems. Look for: tree/graph traversal, nested structures, divide and conquer.

Pattern Recognition Checklist

Use Recursion When

Tree/graph traversal (DFS)
Nested or hierarchical structures
Divide and conquer algorithms
Backtracking problems
Mathematical sequences (factorial, fibonacci)
Subproblems have same structure as original

Don't Use When

Simple iteration suffices
Large input (stack overflow risk)
No natural subproblem structure
Tail recursion can be converted to loop

Recursion Types

Type	Description	Example
Linear	One recursive call	Factorial, sum of array
Binary	Two recursive calls	Fibonacci, binary tree
Multiple	Many recursive calls	N-ary tree traversal
Mutual	Functions call each other	Even/odd check
Nested	Recursive call in argument	Ackermann function
Tail	Recursive call is last operation	Optimizable to iteration

The Three Laws of Recursion

A recursive function must have a base case
A recursive function must change state toward the base case
A recursive function must call itself

When to Use

Tree/Graph Traversal

DFS, preorder, inorder, postorder

Divide and Conquer

Merge sort, quick sort

Backtracking

Permutations, combinations

Dynamic Programming

Top-down memoization

The Recursive Template

def recursive_function(problem):
    # Base case(s) - when to stop
    if is_base_case(problem):
        return base_solution
    
    # Recursive case - break down and solve
    smaller_problem = reduce(problem)
    sub_result = recursive_function(smaller_problem)
    
    # Combine results
    return combine(sub_result, current_work)

Pattern Variations

1. Simple Recursion (Factorial)

def factorial(n):
    """Base case + single recursive call"""
    if n <= 1:
        return 1
    return n * factorial(n - 1)

2. Tree Recursion (Fibonacci)

def fibonacci(n, memo={}):
    """Multiple recursive calls (memoized)"""
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

3. Tail Recursion

def factorial_tail(n, acc=1):
    """Last operation is recursive call - can be optimized"""
    if n <= 1:
        return acc
    return factorial_tail(n - 1, n * acc)

4. Helper Function Pattern

def solve_problem(input_data):
    """Public API, calls recursive helper"""
    result = []
    
    def helper(state, index):
        if is_complete(state):
            result.append(state[:])
            return
        
        for choice in get_choices(index):
            state.append(choice)
            helper(state, index + 1)
            state.pop()
    
    helper([], 0)
    return result

5. Binary Tree Traversal

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root):
    """Left -> Root -> Right"""
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

def max_depth(root):
    """Height of binary tree"""
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Classic Problems

Problem	Pattern	Key Insight
Factorial	Simple	One recursive call
Fibonacci	Tree + Memo	Multiple calls, cache results
Tower of Hanoi	Mutual	Move n-1, move 1, move n-1
Tree Traversal	Binary	Left subtree, root, right
Permutations	Backtrack	Choose, explore, unchoose

Common Mistakes

Avoid These Pitfalls:

Missing base case: Leads to infinite recursion and stack overflow
Base case never reached: State doesn’t progress toward termination
Wrong return value: Not combining subproblem results correctly
Modifying shared state: Forgetting to backtrack in backtracking
Stack overflow: Too deep recursion without memoization or tail call

Debugging Recursion

Verify Base Case

Is there at least one base case? Does it return correct value?

Check Progress

Does each recursive call move toward the base case?

Trace Small Input

Manually trace with n=0, n=1, n=2 to verify logic

Add Print Statements

Print entry/exit to visualize call stack

Consider Memoization

If same subproblems repeat, add caching

Interview Problems by Company

Easy
Medium
Hard

Problem	Company	Key Concept
Fibonacci	All	Binary recursion + memo
Reverse String	Amazon	Two-pointer recursion
Merge Two Lists	All FAANG	Linked list recursion
Maximum Depth of Tree	All	Binary tree recursion

Problem	Company	Key Concept
Pow(x, n)	Meta, Google	Fast exponentiation
Decode String	Google, Amazon	Nested recursion
Flatten Nested List	Meta	Iterator + recursion
Letter Combinations	All FAANG	Backtracking

Problem	Company	Key Concept
Regular Expression	Google, Meta	Two-branch recursion
Wildcard Matching	Google	Recursion + memo
Parse Boolean Expr	Amazon	Nested expression

Interview Tips

How to Explain Your Approach

Script for interviews:

“I’ll solve this recursively because it breaks into smaller self-similar subproblems.”
“My base case is [describe when to stop].”
“My recursive case [describe how to break down].”
“I combine results by [describe combination].”
“Time complexity is O(X) because [reasoning].”

Recursion vs Iteration

Aspect	Recursion	Iteration
Readability	Often cleaner for trees	Better for simple loops
Memory	Stack frames	Usually O(1)
Performance	Function call overhead	Generally faster
When to choose	Complex branching	Simple linear process

Converting to Iteration

Many recursive solutions can use explicit stack:

# Recursive
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Iterative with stack
def preorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

Practice Problems

Pow(x, n)

Fast exponentiation recursion

K-th Symbol

Pattern recognition recursion

Flatten Nested List

Recursive flattening

Decode String

Nested structure recursion

Practice Roadmap

Day 1: Basic Recursion

Solve: Fibonacci, Factorial, Sum of Array
Focus: Base case + recursive case pattern

Day 2: Tree Recursion

Solve: Max Depth, Same Tree, Invert Tree
Focus: Binary tree traversal patterns

Day 3: Divide and Conquer

Solve: Pow(x, n), Merge Sort
Focus: Splitting and combining

Day 4: Advanced Recursion

Solve: Decode String, Regular Expression
Focus: Complex nested structures

Interview Tip: If you’re stuck on recursion, start by asking: “What’s the smallest version of this problem I can solve directly?” That’s your base case.

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

What is Recursion?

Pattern Recognition Checklist

Use Recursion When

Don't Use When

Recursion Types

The Three Laws of Recursion

When to Use

Tree/Graph Traversal

Divide and Conquer

Backtracking

Dynamic Programming

The Recursive Template

Pattern Variations

1. Simple Recursion (Factorial)

2. Tree Recursion (Fibonacci)

3. Tail Recursion

4. Helper Function Pattern

5. Binary Tree Traversal

Classic Problems

Common Mistakes

Debugging Recursion

Interview Problems by Company

Interview Tips

Practice Problems

Pow(x, n)

K-th Symbol

Flatten Nested List

Decode String

Practice Roadmap

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

​What is Recursion?

​Pattern Recognition Checklist

Use Recursion When

Don't Use When

​Recursion Types

​The Three Laws of Recursion

​When to Use

Tree/Graph Traversal

Divide and Conquer

Backtracking

Dynamic Programming

​The Recursive Template

​Pattern Variations

​1. Simple Recursion (Factorial)

​2. Tree Recursion (Fibonacci)

​3. Tail Recursion

​4. Helper Function Pattern

​5. Binary Tree Traversal

​Classic Problems

​Common Mistakes

​Debugging Recursion

​Interview Problems by Company

​Interview Tips

​Practice Problems

Pow(x, n)

K-th Symbol

Flatten Nested List

Decode String

​Practice Roadmap

What is Recursion?

Pattern Recognition Checklist

Recursion Types

The Three Laws of Recursion

When to Use

The Recursive Template

Pattern Variations

1. Simple Recursion (Factorial)

2. Tree Recursion (Fibonacci)

3. Tail Recursion

4. Helper Function Pattern

5. Binary Tree Traversal

Classic Problems

Common Mistakes

Debugging Recursion

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap