Recursion

Overview

The idea

A recursive function solves a problem by handing a smaller copy of the same problem to itself, then using the answer. It needs two parts and one guarantee, and it breaks without any of them.

| Part | What it does | Factorial example | |---|---|---| | Base case | answers the smallest input directly, with no further call | n [!TIP] > Recursion depth equals the tree height. A balanced tree of a million nodes is about 20 levels deep, but a skewed one (a sorted insert into a plain binary search tree) is a million levels deep. Ask about the input shape before you promise recursion is safe.

The five shapes you will meet

• Linear — 1 — use one smaller answer — Reverse String, Merge Two Sorted Lists, Pow(x, n)
• Divide and conquer — 2 or more, on disjoint halves — merge the halves — Sort List, Different Ways to Add Parentheses
• Tree recursion — one per child — combine child results — Maximum Depth, Lowest Common Ancestor
• Backtracking — one per choice — record full solutions, undo the choice — Subsets, Permutations, Generate Parentheses
• Memoized — several, overlapping — store and reuse — Fibonacci, Regular Expression Matching

Backtracking has its own topic, and so does dynamic programming. This topic is the base both build on.

Spotting a recursive problem

• Input is a tree, or a nested structure (brackets, JSON, directories) — tree recursion on each child
• The answer for n is built from the answer for n - 1 or n / 2 — linear recursion
• Split in half, solve each half, join — divide and conquer
• Generate all combinations, subsets or arrangements — backtracking
• The same subproblem appears on many branches — recursion plus a memo

What you will be able to do

• Write any recursive function by naming its base case, its shrink step and its combine step.
• Trace a call stack on a small input and state the stack space it uses.
• Estimate time from the recursion tree, and recognize the common recurrences.
• Add memoization when subproblems repeat, and explain the drop in cost.
• Rewrite a recursive solution as a loop when the depth could be too large.

When to use it

• Walking a tree or graph, where each child is a smaller copy of the same problem
• Divide and conquer: merge sort, quicksort, fast power
• Generating all subsets, combinations or permutations (backtracking)
• Parsing nested input such as brackets or encoded strings (Decode String)
• Any problem where the answer for n is built from answers for smaller inputs
• As the first step toward dynamic programming: write the recursion, then add a memo

More Coding & DSA topics

• Multi-Threaded Coding
• Ordered Set
• Palindromic Subsequence DP
• Prefix Sum
• Queues
• QuickSort / QuickSelect
• Search Algorithms
• Segment Tree & Fenwick Tree
• Shortest Path Algorithms
• Sliding Window
• Sorting Algorithms
• Stacks