Recursion

A function that calls itself is recursive. Recursion is the natural fit for problems that break down into a smaller version of the same problem: walking a tree, computing a factorial, parsing a nested structure.

Factorial, the canonical example

n! (read "n factorial") is the product of all positive integers up to n. 5! is 5 * 4 * 3 * 2 * 1 = 120. You could compute it with a for loop, but the recursive definition is short:

• factorial(0) is 1 (the base case, by convention)
• factorial(n) is n * factorial(n - 1) for any positive n

Translated to Go:

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

func main() {
    fmt.Println(factorial(5))   // 120
}

Every recursive function has two parts you have to get right:

1. The base case. A value for which the answer is known directly, without further recursion. For factorial, n == 0 returns 1. Without a base case, the function calls itself forever and eventually crashes.
2. The recursive step. A rule that expresses the answer for n in terms of a smaller value. For factorial, n * factorial(n - 1) reduces the problem by one each call, which guarantees the base case is eventually reached.

Get either wrong and the function never terminates, or it returns nonsense. Tracing a recursive function by hand for a small input (factorial(3), factorial(2), factorial(1), factorial(0)) is the fastest way to see both parts in action.

Fibonacci, a less efficient example

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, ... where each number is the sum of the previous two. The recursive definition mirrors that:

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

func main() {
    fmt.Println(fib(10))   // 55
}

This works, but it is much slower than it looks. Each call spawns two new calls, those spawn four, those spawn eight. Most of those calls recompute subproblems the program has already answered.

You can see the explosion yourself by adding a counter:

var calls int

func fib(n int) int {
    calls++
    if n < 2 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

func main() {
    result := fib(10)
    fmt.Println("fib(10) =", result, "after", calls, "calls")
    // fib(10) = 55 after 177 calls
}

177 calls to produce the tenth Fibonacci number. And the damage grows fast: fib(20) needs over twenty thousand calls, fib(30) over two million, fib(40) over three hundred million. The runtime is exponential in n.

An iterative version (a for loop that tracks the two most recent values) computes fib(10) in ten steps and fib(40) in forty. Recursion is a nice way to express the definition; it is not always the right shape for the implementation. When a naive recursion keeps recomputing the same subproblem, reach for a loop or for memoisation (caching results by input).

Each recursive call adds another layer

When one function calls another, Go has to remember where to come back to when that inner call finishes. Recursion stacks that work up.

With factorial(5), the program has to remember:

• after factorial(4) finishes, multiply by 5
• after factorial(3) finishes, multiply by 4
• after factorial(2) finishes, multiply by 3
• after factorial(1) finishes, multiply by 2

That stack of unfinished calls is called the call stack. Each recursive call adds another layer to it.

Some languages can optimise a narrow kind of recursion by turning it into a loop automatically. That is called tail-call optimisation. Go does not do that, so a recursive call is still a real function call that uses more stack space.

That means deeply recursive functions can blow the stack. Go's goroutine stacks start small and grow on demand, so everyday recursion depths are fine. Still, if the recursion depth is bounded by user input (walking a deeply nested JSON tree, for example), an iterative version is the safer choice.

For the small recursion depths in textbook examples (factorial, Fibonacci, a walk over a tree with a few thousand nodes), Go's recursion is perfectly safe.

7
6
15