Recursion

A function calls itself to solve a smaller instance of the same problem. That self-call is the defining feature of recursion, and it can turn a complex problem into a straightforward, almost declarative piece of code. Go supports recursive functions like most languages, but it does not optimize them at the compiler level — a fact that shapes when and how recursion should be used.

What Problem Recursion Solves

Some problems are naturally self-similar: a directory contains files and more directories, a JSON object can nest other objects, a mathematical expression contains sub‑expressions. Iterative solutions to these problems often require explicit stack management that mirrors what the call stack does automatically during recursion.

Recursion hands the bookkeeping to the language runtime. Each recursive call creates a new frame on the call stack that remembers where it came from and what partial result it holds. This lets you focus on the logic of the problem rather than on manually tracking state.

The Two Required Parts of Every Recursive Function

A recursive function in Go always has two pieces, and neither is optional.

1. Base case — the stopping condition
This is the simplest possible input, the one where the answer is already known without further recursion. When the function detects the base case, it returns immediately without calling itself. Without it, the function never stops.

2. Recursive step — the self-call that moves toward the base case
The function does a small piece of work and then calls itself with arguments that are strictly closer to the base case. The call chain must make measurable progress; otherwise, the base case is never reached.

How the Call Stack Handles Recursion

When main calls a recursive function, Go pushes a frame onto the goroutine’s stack that holds the function’s arguments and local variables. That frame stays alive until the function returns. If the function calls itself, a second frame is stacked on top. This repeats until the base case is hit; then the frames start popping off, each returning its result to the caller below it.

The following Stepper walks through what happens with a simple factorial(4) function.

A beginner can picture the process as a stack of sticky notes: each note says “multiply my number with the result from the note above me; wait for that note to disappear before I do my multiplication.” The top note never delegates; it knows the answer outright.

A Straightforward Factorial Function

The factorial of a non‑negative integer n, written n!, is the product of all positive integers up to n. By definition, 0! = 1. The recursive definition — n! = n × (n-1)! — translates directly into Go.

func Factorial(n int) int {
    if n == 0 {
        return 1
    }
    return n * Factorial(n-1)
}

Calling Factorial(4) returns 24. The function is concise because the problem itself is recursive. A loop would need an explicit accumulator variable; here, the intermediate results are held on the stack.

Where Recursion Earns Its Keep — Tree‑Shaped Data

Factorial is a pedagogical example. The place recursion becomes genuinely indispensable is with nested, recursive data structures: file systems, JSON documents, comment threads, abstract syntax trees, and DOM‑like structures.

Consider a simple file‑system tree print. Each directory contains entries; each subdirectory is itself a directory. The structure is self‑similar, and recursion collapses the traversal logic into a handful of lines.

func PrintTree(path string, indent string) error {
    entries, err := os.ReadDir(path)
    if err != nil {
        return err
    }
    for _, entry := range entries {
        fmt.Printf("%s%s\n", indent, entry.Name())
        if entry.IsDir() {
            PrintTree(filepath.Join(path, entry.Name()), indent+"  ")
        }
    }
    return nil
}

PrintTree does not know how deep the tree goes; it just does the same thing for every directory it encounters. An iterative version would require an explicit stack ([]string for directories to visit), essentially recreating what the call stack does for free.

A binary tree traversal follows the same pattern:

type Node struct {
    Value int
    Left  *Node
    Right *Node
}
func PreOrder(n *Node) {
    if n == nil {
        return
    }
    fmt.Println(n.Value)
    PreOrder(n.Left)
    PreOrder(n.Right)
}

The base case is a nil node. The recursive step visits the left subtree, then the right. This three‑line function would become a manual stack‑management exercise without recursion.

Recursive Patterns You Will Encounter

Understanding the shape of a recursive function helps you decide which pattern fits.

Single (Linear) Recursion

The function calls itself once per invocation. Factorial and PrintTree are linear‑recursive: one branch of execution, one self‑call. The call stack depth equals the depth of the recursion.

Multiple (Binary) Recursion

The function calls itself more than once. Fibonacci is the classic example:

func Fib(n int) int {
    if n <= 1 {
        return n
    }
    return Fib(n-1) + Fib(n-2)
}

Two recursive calls create an exponential number of total calls. Computing Fib(40) this way does an enormous amount of repeated work because the same values are recomputed many times.

Head vs. Tail Recursion

The naming refers to where the recursive call sits inside the function body.

• Head recursion: the recursive call happens early, before other processing. Any logic after the call executes during the unwind phase.
• Tail recursion: the recursive call is the very last operation, with no pending work after it. The result of the recursive call is returned directly.

Tail recursion is interesting because some compilers can optimize it into a loop, reusing the same stack frame. Go does not perform tail‑call optimization. A tail‑recursive Go function will still grow the stack for every call.

// Tail-recursive factorial with an accumulator.
func TailFactorial(n, acc int) int {
    if n == 0 {
        return acc
    }
    return TailFactorial(n-1, acc*n)
}

TailFactorial(4, 1) returns the correct result, but the Go runtime will push a new frame for each recursive call just like the original version. The stack depth is identical.

Indirect Recursion

Function A calls B, and B calls A — or a longer cycle. This appears in parsers, state machines, and some mathematical algorithms.

func IsEven(n int) bool {
    if n == 0 {
        return true
    }
    return IsOdd(n - 1)
}
func IsOdd(n int) bool {
    if n == 0 {
        return false
    }
    return IsEven(n - 1)
}

Indirect recursion works fine in Go as long as the cycle eventually hits a base case.

Anonymous Function Recursion

Anonymous functions can be recursive, but the function literal must be assigned to a variable first so that the body can refer to the variable by name.

var factorial func(int) int
factorial = func(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorial(n-1)
}
fmt.Println(factorial(5)) // 120

The declaration var factorial func(int) int creates a named slot; the literal then closes over that variable, allowing the self‑call. Without the separate declaration, the literal cannot reference itself because := would not yet have bound the name.

Common Pitfalls and How to Avoid Them

The table below collects the mistakes that appear most often in real Go code reviews.

Summary

Recursion in Go is a direct, predictable mechanism: every call pushes a frame, the base case triggers unwinding, and the result bubbles back up. The language does not try to hide the stack or transform your code into something more efficient — what you write is what happens at runtime.

The biggest takeaway is to match the tool to the shape of the problem. When your data is recursive, recursion will usually produce the smallest, most self‑evident code. When your data is flat, or when the recursion depth might grow arbitrarily large (user‑supplied input, unbounded directory depth), an iterative approach is the safer choice. For problems like Fibonacci where binary recursion causes massive repeated work, add memoization or fall back to a loop.

If you’ve internalised how the call stack grows and unwinds, you’re ready to use recursion with confidence.