Recursion

Some problems are convenient to describe through themselves. The factorial of a number n is the product of all numbers from 1 to n. It is defined by two rules:

• the factorial of zero is 1;
• the factorial of n is n times the factorial of n - 1.

A Go function repeats this definition word for word by calling itself:

package main

import "fmt"

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

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

Let's go back to the kitchen appliance and see how it computes factorial(5):

1. The factorial appliance got 5, but it doesn't know the answer right away.
2. It sets up an identical appliance next to it, hands it 4 and waits for the dish, to multiply it by 5.
3. The second appliance passes the work to a third one with 3 in the same way, and so on down to the appliance that got 0.
4. That last one answers 1 at once, without calling anyone.

Two branches of a recursive function

Recursion is a function calling itself. Each call gets its own copy of the parameter n, the way each appliance gets its own portion. So factorial(5), factorial(4) and the other calls do not interfere with each other.

A recursive function always has two branches. Let's look at each.

The base case

The branch in which the function finishes without recursing is called the base case. In factorial it is if n == 0 { return 1 }: the call factorial(0) returns 1 at once, without a new call.

Without a base case the calls never end. It must be reachable: every recursive step has to bring the argument closer to it.

The recursive step

The line return n * factorial(n-1) calls the same function with an argument one smaller. The call factorial(5) waits for the result of factorial(4), which waits for factorial(3), and so on down to factorial(0).

Then the results travel back up the chain:

1. factorial(0) returns 1.
2. factorial(1) returns 1 * 1, that is 1.
3. factorial(2) returns 2 * 1, that is 2.
4. factorial(3) returns 3 * 2, that is 6.
5. factorial(4) returns 4 * 6, that is 24.
6. factorial(5) returns 5 * 24, that is 120.

Here the analogy stops working: you would need six real appliances, while the program has one function. What is kept separately for each call is only its data—the parameter n and the place to return the result to.

The call stack

Until a call finishes, its parameters and the place to return the result to are kept in memory. This memory area is called the stack, and each unfinished call takes its own record in it.

The stack is like a pile of plates:

• a new call puts a plate on top;
• a finished call takes the top plate off.

Press "Next step" and watch the pile of frames grow down to factorial(0) and then come off from the top. To fit the pile on the screen, this one computes factorial(3).

At the deepest point of factorial(5) the stack holds six records of factorial calls. The stack in Go grows as needed, but not without limit: on 64-bit systems its limit is 1 GB.

Tail calls

Some languages turn a recursive call that is the function's last action into a loop, and the stack does not grow. This rewrite is called tail call optimization, and Go does not do it: every recursive call adds a new record to the stack.

Interviewers like to ask this: "Does Go have tail call optimization?" The answer has three parts:

• no, Go does not do it;
• so recursion uses up stack on every level;
• when the depth can reach millions of calls, you write a loop instead of recursion.

A loop instead of recursion

The same factorial as a loop:

func factorialLoop(n int) int {
    result := 1
    for i := 2; i <= n; i++ {
        result = result * i
    }
    return result
}

The loop makes no new calls: the variables result and i change in place. However many steps there are, the pile of plates does not grow.

Common mistake

A recursive function was called with an argument from which the base case cannot be reached:

fmt.Println(factorial(-1)) // ✗

fatal error: stack overflow

From -1 the chain goes to -2, -3 and further, and n == 0 never comes. Each call adds a record until the stack hits its limit, and the program crashes. Make sure the base case can be reached from every valid argument, and reject invalid arguments before the recursion starts.

Key points

• A recursive function calls itself and needs a base case that finishes without a new call.
• Each unfinished call takes a record on the stack, and the stack in Go is limited.
• Go does not do tail call optimization, so very deep recursion is written as a loop.