Recursion Basics

One-liner: recursion solves a problem by solving a slightly smaller copy of the same problem, and stops at a case so small the answer is obvious.

The analogy

Russian nesting dolls. To find out how many dolls are inside, you open the biggest one and ask the same question of the doll inside it. That doll opens the next, and so on, until you reach the smallest doll, which has nothing inside (the base case). Then the answers travel back out: "0 inside", so this one holds 1, so the next holds 2, and so on. Every doll does the same small job and trusts the doll inside to answer for itself.

Recognition signals

1. The problem contains a smaller version of itself: a tree is a root plus smaller trees, a list is a first item plus a shorter list.
2. You need to try every choice and each choice leaves a smaller problem (Backtracking).
3. The answer is defined in terms of earlier answers (fib(n) = fib(n-1) + fib(n-2)), which later becomes dynamic programming.
4. The data is nested or branching, such as trees and folders, where a loop would need its own stack.

Step-by-step walkthrough

Factorial(3) means 3 × 2 × 1. Follow the calls down, then the answers back up:

1. Factorial(3) is not a base case. It calls Factorial(2) and waits.
2. Factorial(2) calls Factorial(1) and waits.
3. Factorial(1) is the base case: it returns 1 straight away.
4. Back in Factorial(2): 2 × 1 = 2, return 2.
5. Back in Factorial(3): 3 × 2 = 6, return 6.

While Factorial(3) waits, the computer remembers it on the call stack, a pile with one entry per unfinished call. Calls pile up on the way down and are removed on the way back.

Code template

// Factorial: n! = n × (n-1)!  — a big problem defined by a slightly smaller copy of itself.
func Factorial(n int) int {
	if n <= 1 { // 1. base case: the smallest problem, answered directly. Without it the calls never stop.
		return 1
	}
	return n * Factorial(n-1) // 2. trust the smaller call, 3. combine its answer with this level's work
}

See the call stack

Trace logs when each call starts and ends. Notice the order: every enter comes before any exit, and the exits come back in the reverse order.

// Trace records when each call starts and finishes, so you can see the call stack grow and unwind.
// Calls "go down" until the base case, then answers come back up in the opposite order.
func Trace(n int) []string {
	var log []string
	var walk func(int)
	walk = func(k int) {
		log = append(log, fmt.Sprintf("enter %d", k))
		if k > 0 {
			walk(k - 1)
		}
		log = append(log, fmt.Sprintf("exit %d", k))
	}
	walk(n)
	return log
}

For Trace(2) the log is enter 2, enter 1, enter 0, exit 0, exit 1, exit 2. The last call to start is the first to finish, which is exactly how a stack of plates behaves (Stack Basics).

The real solutions

Sum of a list — the sum is the first number plus the sum of the rest:

// SumList adds the numbers in a slice: the sum is the first number plus the sum of everything after it.
func SumList(nums []int) int {
	if len(nums) == 0 {
		return 0 // nothing left to add
	}
	return nums[0] + SumList(nums[1:])
}

Reverse a string — the reverse of the rest, then the first letter at the end:

// Reverse flips a string: the reverse is the reverse of the rest, followed by the first letter.
func Reverse(s string) string {
	if len(s) <= 1 {
		return s
	}
	return Reverse(s[1:]) + s[:1]
}

Power by halving — the same idea as Pow(x, n). Compute the half once and reuse it:

// Power computes x^n by halving the exponent each call, so 2^1000 needs about 10 calls, not 1000.
func Power(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	half := Power(x, n/2) // computed ONCE and reused: calling Power twice here would undo the speed-up
	if n%2 == 0 {
		return half * half
	}
	return half * half * x
}

When recursion repeats work — FibSlow recomputes the same values again and again (21,891 calls for n = 20). FibMemo stores each answer the first time, so there are only about 2n calls. That one change is the whole idea of dynamic programming:

// FibSlow shows why recursion can explode: fib(n) calls fib(n-1) and fib(n-2), and those repeat the same work.
// calls counts every invocation so you can see the growth.
func FibSlow(n int, calls *int) int {
	*calls++
	if n < 2 {
		return n
	}
	return FibSlow(n-1, calls) + FibSlow(n-2, calls)
}

// FibMemo remembers answers it has already computed, so each n is solved once: the idea behind dynamic programming.
func FibMemo(n int, memo map[int]int) int {
	if n < 2 {
		return n
	}
	if v, ok := memo[n]; ok {
		return v
	}
	memo[n] = FibMemo(n-1, memo) + FibMemo(n-2, memo)
	return memo[n]
}

Complexity

Recursion is never free in memory: each unfinished call takes a slot on the stack, so the depth of the recursion is part of the space cost.

Common mistakes

Practice ladder

Start with the first two in this page's code, then solve these. For each, say the base case out loud before writing anything.

1. 1.
   Climbing Stairs

   How many ways to reach step n, given the ways to reach the two steps before it?
   Easy
2. 2.
   Reverse Linked List

   Reverse the rest of the list first, then fix one pointer.
   Easy
3. 3.
   Maximum Depth of Binary Tree

   What is the depth of an empty tree?
   Easy
4. 4.
   Invert Binary Tree

   Assume both subtrees are already inverted.
   Easy
5. 5.
   Pow(x, n)

   Halve the exponent and reuse the result.
   Medium
6. 6.
   Generate Parentheses

   Each call adds one character; when is each character allowed?
   Medium

When these feel natural, continue with Trees, where almost every solution is a three-line recursive function.

Which pattern? Drills