Before you begin
Why this matters
Recursion is how programs handle data that contains smaller copies of itself, such as folders inside folders or trees of values. If you can follow one call at a time, you can predict what a recursive function prints and find out why one never stops.
What this helps you reason about
- Spot a function that can never stop calling itself, before you run the code.
- Predict the order of work done before and after a function calls itself.
- Choose a loop when the number of nested calls would grow with the size of the input.
A recursive function solves a problem by calling itself on a smaller version of the same problem. In Go, each call gets its own copies of its arguments, which makes recursive calls easy to follow one at a time.
Already know this? The short version
- Each call gets its own frame with copies of its arguments, and the caller waits until that call returns.
- A base case must exist and be reachable from every value the parameter type allows; for an unsigned type, n - 1 at 0 wraps to the largest value instead of going negative.
- Statements before the recursive call run on the way down, outermost call first; statements after it, and deferred calls, run on the way back, innermost call first.
- Go has no tail-call elimination; goroutine stacks grow up to 1 GB on 64-bit systems by default (runtime/debug.SetMaxStack), and an overflow is a fatal error that recover cannot catch.
- values[1:] shares the underlying array, so recursing on smaller slices copies nothing; still, prefer a loop when depth grows with the input.
Words in this lesson (7)
- recursive function
- A function that calls itself. Each call works on a smaller version of the same problem.
- frame
- The record of one function call that has not finished: its parameters and local variables. It is created when the call starts and removed when the call returns.
- call stack
- The frames of all calls in one goroutine that have not finished yet, with the newest on top. A new call adds a frame on top, and a return removes it. Only the newest call runs; each call below it waits for the call it made.
- base case
- The case, an input or a condition such as n == 0, that the function answers without calling itself. Reaching it stops the chain of calls.
- recursive case
- An input the function answers by calling itself on a smaller input and then using that answer.
- goroutine
- A function running on its own, with its own stack. main runs in a goroutine too.
- stack overflow
- The failure when calls go so deep that the call stack runs out of space. In Go the program stops with fatal error: stack overflow.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / A call to itself
What happens when a function calls itself?
A recursive function is a function that calls itself. Each of those calls is a separate call: it gets its own copy of its parameters and keeps them until it finishes.
countdown(3) prints 3 and calls countdown(2). That call prints 2 and calls countdown(1), and so on. Picture each active call as a box placed on top of the call that made it. Each box is called a frame: it holds one call’s parameters and local variables. The pile of frames is called the call stack. When a call finishes, its frame is removed, and the call underneath it continues.
The stepper shows the same picture. Its frame list has one frame for each active call, with the newest call at the top.
func countdown(n int) {
if n == 0 {
fmt.Println("liftoff")
return
}
fmt.Println(n)
countdown(n - 1)
}Every call to countdown is a separate call with its own n.
Precisely: the stack is a model
Go specifies that arguments are evaluated and copied into the called function’s parameters, and that a return resumes the caller. Each goroutine does have its own stack in the Go runtime, but which values live in it is the compiler’s decision.
Experiment
Follow a countdown to its base case
Each call to countdown is a separate call with its own parameter. A call does not finish until the call it made has finished. So countdown(3) waits for countdown(2), countdown(2) waits for countdown(1), and countdown(1) waits for countdown(0).
Why it matters You can follow any recursive function the same way: one call at a time, each with its own values.
Predict how many countdown calls are active when liftoff prints. Then delete the base case (the whole if block) and run again.
package main
import "fmt"
func countdown(n int) {
if n == 0 {
fmt.Println("liftoff")
return
}
fmt.Println(n)
countdown(n - 1)
}
func main() {
countdown(3)
}
What to look for
Watch the frame list: each call to countdown adds one frame, with its own n. Without the base case, n goes below 0 and new frames keep appearing. The runner then ends the run with a message that begins "Stopped after". You will not see fatal error: stack overflow: the runner stops long before the real stack runs out. The frame list shows only the newest 20 calls, so after that it stops growing. Watch n and the output instead: they keep falling.
Expected output
3
2
1
liftoff02 / Base case
What makes the recursion stop?
The base case is the case, an input or a condition, that the function answers directly, without calling itself. Every other input is the recursive case: the function calls itself with a smaller input. Without a base case, every call makes another call, and the program cannot finish on its own.
The calls must also reach the base case. countdown(n - 1) makes n smaller by one each time, so any positive int reaches 0. But with the test n == 0, countdown(-1) calls countdown(-2), then countdown(-3), and never reaches 0. The test n <= 0 makes every starting number stop.
func countdown(n int) {
if n <= 0 {
fmt.Println("liftoff") // base case: answer directly
return
}
fmt.Println(n)
countdown(n - 1) // recursive case: a smaller input
}Check two things: a base case exists, and every call gets closer to it.
Precisely: an unsigned n
If n were a uint, it could never be negative, but n - 1 at 0 would wrap around to the largest uint value. The calls would continue from there. Choose the parameter type so the base case is reachable from every value it allows.
03 / The way back
What happens after the recursive call returns?
A recursive call pauses the current call; it does not end the current call. When visit(2) finishes, visit(3) continues from the line after its recursive call.
So work written before the recursive call happens on the way down, while calls are still being made: visit(3) first, then visit(2), then visit(1). Work written after it happens on the way back, while the calls are returning and each paused call continues: visit(1) first, then visit(2), then visit(3).
func visit(level int) {
if level == 0 {
return
}
fmt.Println("enter", level)
visit(level - 1)
fmt.Println("leave", level)
}Code before the recursive call runs on the way down; code after it runs on the way back.
Coming from Java: defer works like a finally block for the whole function: each recursive call’s deferred work runs when that call returns. Two things differ. Several defers in one function run in reverse order, last in, first out. And a deferred call’s arguments are evaluated when the defer line runs, so defer fmt.Println("leave", level) prints the value level had then, even if level changes later.
Precisely: defer runs on the way back too
A deferred call runs when its surrounding function returns. defer fmt.Println("leave", level) placed before the recursive call would still print on the way back, because each call’s deferred work waits for that call to finish.
Experiment
Watch work happen on the way back
Each visit call prints its enter line, then makes its recursive call and pauses there. It prints its leave line only after the call it made has returned. So the newest call, visit(1), is the first to print leave.
Why it matters Where you put work relative to the recursive call decides its order. This is how a recursive function can reverse a sequence without a separate reverse step.
Predict the order of all six lines before running. Then move the leave line above the recursive call and predict again.
package main
import "fmt"
func visit(level int) {
if level == 0 {
return
}
fmt.Println("enter", level)
visit(level - 1)
fmt.Println("leave", level)
}
func main() {
visit(3)
}
What to look for
Watch the output panel and the frame list together. The enter lines appear while frames are added: visit(3), then visit(2), then visit(1). The leave lines appear as frames are removed: leave 1 first, then leave 2, then leave 3. After the edit, each leave line comes right after its enter line, while calls are still being made: enter 3, leave 3, enter 2, leave 2, enter 1, leave 1.
Expected output
enter 3
enter 2
enter 1
leave 1
leave 2
leave 304 / Combining results
How do the answers come together?
Most recursive functions return a value. Each call asks a smaller version of the question and uses the answer. values[1:] is the part of the slice after the first element, so the total of [4, 2, 7] asks for the total of [2, 7], which asks for [7], which asks for an empty slice. The empty slice is the base case: its total is 0.
The answers come back in reverse order: 0, then 7, then 9, then 13. Each addition waits until the call it depends on has returned.
func total(values []int) int {
if len(values) == 0 {
return 0
}
rest := total(values[1:])
return values[0] + rest
}Assume the smaller call returns the right answer, then use it.
Coming from Python: Python’s values[1:] copies the list; Go’s values[1:] shares the same underlying array and copies nothing.
Precisely: values[1:] does not copy
values[1:] is a new slice that shares the same underlying array. No elements are copied, so passing smaller slices into recursive calls is cheap.
Experiment
Combine results from smaller calls
Each call answers a smaller version of the question and then uses that answer. The base case answers the smallest version directly. The results are combined on the way back, starting from the base case.
Why it matters You do not need to follow every call to check a recursive function. Check that the base case is right. Then check that each call combines a correct smaller answer correctly.
Predict what each call returns before running. Then change the 2 in the list to 5 and predict the new total.
package main
import "fmt"
func total(values []int) int {
if len(values) == 0 {
return 0
}
rest := total(values[1:])
return values[0] + rest
}
func main() {
fmt.Println(total([]int{4, 2, 7}))
}
What to look for
When the base case returns, select each earlier frame in turn. Each frame keeps its own values and receives the smaller call’s result as rest. After the edit, the run prints 16.
Expected output
1305 / Depth
How deep can it go, and when is a loop better?
Each frame takes some memory. In Go, the frames live on the stack of a goroutine: a function running on its own, as main does. Go starts each goroutine with a small stack and grows it as needed, up to a limit of 1 GB on 64-bit systems by default. Past that limit, the program stops with fatal error: stack overflow.
When the depth grows with the size of the input, such as one call per slice element, a loop is usually the clearer choice. Recursion fits best when the data itself is nested, like folders inside folders, where the depth stays small.
func total(values []int) int {
sum := 0
for _, value := range values {
sum += value
}
return sum
}Use recursion when the problem is nested; prefer a loop when depth would grow with the input.
Coming from Java: Java’s StackOverflowError can be caught; Go’s stack overflow is a fatal error that recover cannot catch.
Precisely: no tail-call elimination
The Go compiler does not turn recursive calls into jumps, so even a call in the last position of a function uses a new frame. runtime/debug.SetMaxStack changes the limit; a stack overflow is a fatal error that recover cannot catch.
06 / Try it
Can you follow a fresh example?
Predict the output before revealing the answer. Ask where the print sits relative to the recursive call.
package main
import "fmt"
func show(n int) {
if n == 0 {
return
}
show(n - 1)
fmt.Println(n)
}
func main() {
show(3)
}
What does this print, and why in that order?
Reveal the reasoning
1, then 2, then 3. show(3) calls show(2), which calls show(1), which calls show(0). show(0) returns immediately. Then show(1) continues and prints 1, show(2) prints 2, and show(3) prints 3. The print comes after the recursive call, so it runs on the way back.
Practice tickets
- REC-101 · Fix the parcel check number → Free
- REC-102 · Count every nested folder → Sign in · Pro
- REC-103 · Show the reporting chain → Sign in · Pro