Recursion & the Call Stack

Thinking Recursively

Beginners often try to trace every recursive call in their head and get lost. The productive approach is different: define the problem precisely, handle the smallest case directly, and trust that the recursive call solves the smaller case correctly.

Base Case and Reduction

Every recursive function answers two questions:

• Base case — which input is small enough to answer without recursion? (an empty slice, n = 0, a nil node)
• Reduction — how do I build the answer for this input from the answer for a smaller input?

Every recursive call must move strictly closer to a base case; otherwise the recursion never ends. In the example below the slice shrinks by one element per call until it is empty.

// sum adds all elements of s.
//   base case: the empty slice sums to 0
//   reduction: sum(s) = s[0] + sum(rest of s)
func sum(s []int) int {
	if len(s) == 0 {
		return 0
	}
	// s[1:] is a view of the same backing array, not a copy,
	// so each call does O(1) work besides the recursive call.
	return s[0] + sum(s[1:])
}

The Recursive Leap of Faith

When writing s[0] + sum(s[1:]), do not ask "how does sum(s[1:]) compute its result?". Assume it returns the correct sum of the rest — that is what the function promises — and check only that you combine it correctly. This is mathematical induction applied to code: if the base case is right and each step is right assuming smaller cases are right, the whole function is right.

The Call Stack

Recursion is not magic: it is ordinary function calls. Each call gets a stack frame holding its parameters, local variables, and the place to return to. Frames are pushed when a function is called and popped when it returns, in last-in, first-out order.

At the deepest point of factorial(3), four frames are active. The base case returns 1, and each waiting frame multiplies by its own n as the stack unwinds.

Frames and Local State

Each frame has its own copy of n. When factorial(3) calls factorial(2), the variable n = 3 is not overwritten; it waits in its own frame until the call returns. The demo prints every call and return, indented by depth, so you can watch the stack grow and shrink.

func factorial(n int) int {
	if n <= 1 {
		return 1 // base case
	}
	// this frame pauses here, keeping its own n,
	// until factorial(n-1) returns a value
	return n * factorial(n-1)
}

Full trace program: 05_recursion_trace.go.

Depth and Stack Growth in Go

Recursion depth costs memory: one frame per active call. Goroutine stacks in Go start small (a few kilobytes) and grow automatically, so recursion thousands or even millions of levels deep works. The limit is 1 GB per goroutine on 64-bit systems by default (adjustable with runtime/debug.SetMaxStack). Exceeding it — usually because a base case is missing — ends the program with fatal error: stack overflow.

Go does not perform tail-call elimination, so writing the recursive call as the last statement does not reduce stack usage. If depth can reach the size of the input and the input can be large, prefer an iterative version.

Recursion Patterns

Recursive algorithms differ mainly in how much they shrink the problem and how many recursive calls each level makes. These two numbers determine the cost.

Linear Recursion

One recursive call on an input smaller by a constant. Depth is n, total work is O(n). Examples: sum, factorial, reversing a string, walking a linked list. These are usually clearer as loops in Go, but they are the right first step for learning.

// reverse returns s with its bytes in reverse order (ASCII input).
// reduction: reverse("abc") = reverse("bc") + "a"
// Note: string concatenation copies, so this version is O(n^2) —
// fine for learning, not for long strings.
func reverse(s string) string {
	if len(s) <= 1 {
		return s
	}
	return reverse(s[1:]) + s[:1]
}

Divide and Conquer

Split the input into parts of a fraction of the size, solve them, and combine. Cutting the problem in half each time reduces depth from n to log n. Fast exponentiation computes xⁿ with about log₂ n multiplications instead of n:

// pow computes x^n for n >= 0 in O(log n) multiplications.
func pow(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	half := pow(x, n/2) // compute the half ONCE and reuse it
	if n%2 == 0 {
		return half * half // x^8 = x^4 * x^4
	}
	return half * half * x // x^9 = x^4 * x^4 * x
}

Writing pow(x, n/2) * pow(x, n/2) would make two calls per level and return the cost to O(n). The demo counts calls for both versions and includes the modular form used in cryptography: 06_fast_power.go.

Multiple Branches

When each call makes two or more recursive calls on inputs that shrink by only a constant, the number of calls grows exponentially. The Tower of Hanoi is the classic example: moving n disks requires moving n-1 disks twice, giving 2ⁿ - 1 moves. Here recursion is the clearest way to express the solution, and the exponential cost is inherent to the problem, not a flaw in the code.

The demo generates the moves and verifies every rule by replaying them on three stacks: 07_hanoi.go.

Recursion on Trees

Recursive data calls for recursive code. A directory contains files and directories; its size is its own size plus the size of each child. The function mirrors the data definition exactly, which is why tree algorithms (Phase 2) are almost always written recursively.

// Node is a file (no children) or a directory (with children).
type Node struct {
	Name     string
	Size     int
	Children []*Node
}

// totalSize visits every node once: O(number of nodes).
func totalSize(n *Node) int {
	total := n.Size
	for _, c := range n.Children {
		total += totalSize(c) // trust the call for each subtree
	}
	return total
}

Analyzing Recursive Cost

Loops can be read by counting iterations. Recursive functions need one more tool: an equation that describes the cost in terms of itself.

Recurrence Relations

Write T(n) for the cost on input size n, and express it through the cost of the recursive calls plus the work done in the call itself. Four recurrences cover most algorithms in this roadmap:

Recursion Trees and Repeated Work

Drawing the calls as a tree makes the cost visible: the number of nodes is the number of calls. The naive Fibonacci function fib(n) = fib(n-1) + fib(n-2) produces the tree below.

Naive fib(5) makes 15 calls. Orange nodes repeat work already done elsewhere in the tree: fib(3) is computed twice and fib(2) three times.

The repeated subtrees are the "repeated work" from the problem-solving workflow. Storing each result the first time it is computed — memoization — removes them and makes the function linear. This idea is the core of Dynamic Programming in Phase 4.

// fibMemo computes Fibonacci numbers in O(n) time by caching results.
// memo[k] holds fib(k) once computed; the map is shared by all calls.
func fibMemo(n int, memo map[int]int) int {
	if n < 2 {
		return n // fib(0) = 0, fib(1) = 1
	}
	if v, ok := memo[n]; ok {
		return v // already computed: O(1), no subtree
	}
	v := fibMemo(n-1, memo) + fibMemo(n-2, memo)
	memo[n] = v
	return v
}

// usage: fibMemo(90, map[int]int{}) — instant, while naive fib(90)
// would need about 10^19 calls.

From Recursion to Iteration

Any recursive algorithm can be rewritten as a loop that manages its own stack. The conversion is mechanical once you see that the call stack only stores "what is left to do" and "the state needed to do it".

Explicit Stack

Replace the recursive call with a slice used as a stack: push the starting item, then loop while the stack is not empty — pop one item, process it, push its sub-problems. Any state that the recursive version kept in parameters (such as the current path) must be stored in the stack entries.

// totalSizeIter computes the same result as totalSize without recursion.
func totalSizeIter(root *Node) int {
	total := 0
	stack := []*Node{root} // pending work
	for len(stack) > 0 {
		n := stack[len(stack)-1]     // take the top item
		stack = stack[:len(stack)-1] // pop it
		total += n.Size
		stack = append(stack, n.Children...) // schedule the children
	}
	return total
}

The demo also lists paths in the same depth-first order as recursion and handles a chain one million levels deep: 08_recursive_to_iterative.go.

When to Prefer Iteration

• Linear recursion (one call, shrink by one) is almost always clearer and cheaper as a loop in Go.
• Unbounded depth — a degenerate tree or a long linked chain — risks exhausting the stack; use an explicit stack.
• Pause and resume — iterators that return one element at a time need their state in a data structure, not on the call stack.
• Balanced trees and divide and conquer have O(log n) depth; recursion is safe and usually clearer there.

Common Pitfalls

Recursive bugs tend to be dramatic — infinite loops, stack overflows, exponential slowdowns — but each has a simple cause.

Missing or Unreachable Base Case

factorial(-1) with the base case n == 0 recurses forever: -1, -2, -3, … never reaches 0. Use a base case that covers all small inputs (n <= 1) and reject invalid input explicitly.

Accidental Exponential Cost

Calling the same function twice on the same argument — as in naive Fibonacci or pow(x, n/2) * pow(x, n/2) — multiplies the work at every level. Compute a sub-result once and store it in a variable or a memo table.

Shared Slices Between Calls

Appending to a slice parameter inside recursive calls can overwrite data that another call is still using, because sub-slices share a backing array. When a recursive function builds partial results (paths, subsets), copy the slice before storing it — this becomes essential in Backtracking.

Practice Lab

Practice the two design questions (base case, reduction) until they become automatic.

Run the Demos

1. In 05_recursion_trace.go, add a traced fib and count how many times fib(2) is called for fib(10).
2. In 06_fast_power.go, replace half * half with two recursive calls and compare the call counts.
3. In 08_recursive_to_iterative.go, call totalRecursive on the one-million-level chain — it works, because Go grows the stack. Then add debug.SetMaxStack(1 << 20) (package runtime/debug) at the start of main to cap the stack at 1 MB, run again, and read the fatal error: stack overflow report. The iterative version is unaffected.

Exercises

1. Palindrome. Write isPalindrome(s string) bool recursively using indices lo, hi instead of slicing. State the base case and the reduction.
2. Count digits. Write a recursive function that returns the number of decimal digits of a non-negative integer. What is its recurrence?
3. Flatten. Given type Item struct { Value int; Items []Item }, return all values in depth-first order — first recursively, then with an explicit stack. Check that both produce the same slice.

Next lesson: Data Structures Map.