Recursion

A recursive function calls itself to solve a smaller version of the same problem, until it reaches a case simple enough to answer directly. Recursion is the natural fit for data that contains smaller copies of itself — folders inside folders, trees, nested lists — and for divide-and-conquer algorithms. This lesson covers base cases, how Go's growable stacks handle deep recursion, and when a loop is the better choice.

Base case and recursive case

Every recursive function needs a base case that returns without recursing, and a recursive case that moves closer to it:

package main

import "fmt"

func factorial(n int) int {
	if n <= 1 { // base case
		return 1
	}
	return n * factorial(n-1) // recursive case: a smaller problem
}

func countdown(n int) {
	if n == 0 {
		fmt.Println("liftoff!")
		return
	}
	fmt.Print(n, "... ")
	countdown(n - 1)
}

func main() {
	fmt.Println(factorial(5), factorial(10))
	countdown(3)
}

Output

120 3628800
3... 2... 1... liftoff!

factorial(5) calls factorial(4), which calls factorial(3), and so on down to factorial(1). Then the results multiply back up: 1, 2, 6, 24, 120.

Recursive data

Recursion really shines on nested structures. This function totals the sizes of a folder tree, however deep it goes:

package main

import "fmt"

type Node struct {
	Name     string
	Size     int // for files
	Children []Node
}

func totalSize(n Node) int {
	total := n.Size
	for _, child := range n.Children {
		total += totalSize(child)
	}
	return total
}

func printTree(n Node, indent string) {
	fmt.Printf("%s%s (%d)\n", indent, n.Name, totalSize(n))
	for _, child := range n.Children {
		printTree(child, indent+"  ")
	}
}

func main() {
	root := Node{Name: "project", Children: []Node{
		{Name: "main.go", Size: 1200},
		{Name: "docs", Children: []Node{
			{Name: "guide.md", Size: 5400},
			{Name: "img", Children: []Node{{Name: "logo.png", Size: 20480}}},
		}},
		{Name: "go.mod", Size: 60},
	}}
	printTree(root, "")
}

Output

project (27140)
  main.go (1200)
  docs (25880)
    guide.md (5400)
    img (20480)
      logo.png (20480)
  go.mod (60)

Lesson 57 does this with real folders using filepath.WalkDir.

Divide and conquer

Binary search halves the problem each time, so it needs only about 20 steps for a million items:

package main

import "fmt"

func search(sorted []int, target, lo, hi int) int {
	if lo > hi {
		return -1 // not found
	}
	mid := lo + (hi-lo)/2
	switch {
	case sorted[mid] == target:
		return mid
	case sorted[mid] < target:
		return search(sorted, target, mid+1, hi)
	default:
		return search(sorted, target, lo, mid-1)
	}
}

func main() {
	nums := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
	fmt.Println(search(nums, 23, 0, len(nums)-1))
	fmt.Println(search(nums, 7, 0, len(nums)-1))
}

Output

5
-1

Deep recursion in Go

Each call needs a little memory on the stack. Go's goroutine stacks start small and grow automatically, so recursion thousands or even millions of levels deep works. There is still a limit — 1 GB of stack on 64-bit systems — and a function with no working base case hits it quickly:

package main

import "fmt"

func depth(n int) int {
	if n == 0 {
		return 0
	}
	return 1 + depth(n-1)
}

func main() {
	fmt.Println(depth(1_000_000)) // a million levels: fine
}

Output

package main

func forever(n int) int {
	return forever(n+1) + 1 // no base case
}

func main() {
	forever(0)
}

Output

runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0x22f56fd603a0 stack=[0x22f56fd60000, 0x22f58fd60000]
fatal error: stack overflow

runtime stack:
…
exit status 2

A stack overflow is a fatal error that can't be recovered from, so make sure every path reaches a base case. Go doesn't optimise tail calls, so a recursive function always uses stack space in proportion to its depth.

When to use a loop instead

Naive recursion can redo the same work many times. The textbook Fibonacci function makes an exponential number of calls; a loop (or a cache, as in lesson 33) is dramatically faster:

package main

import "fmt"

var calls int

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

func fibFast(n int) int {
	a, b := 0, 1
	for range n {
		a, b = b, a+b
	}
	return a
}

func main() {
	fmt.Println(fibSlow(30), "using", calls, "calls")
	fmt.Println(fibFast(30), fibFast(90))
}

Output

832040 using 2692537 calls
832040 2880067194370816120

Use recursion when the problem is naturally recursive — trees, nested data, divide and conquer. For straight sequences, a loop is simpler and cheaper.

Try it yourself

Flatten a nested list of numbers into one slice. The nested list uses any, which can hold either an int or another list; a type switch (lesson 41) tells them apart.

package main

import "fmt"

func flatten(items []any) []int {
	var out []int
	for _, it := range items {
		switch v := it.(type) {
		case int:
			out = append(out, v)
		case []any:
			out = append(out, flatten(v)...)
		}
	}
	return out
}

func main() {
	nested := []any{1, []any{2, 3, []any{4, []any{5}}}, 6}
	fmt.Println(flatten(nested))
}

Edit the code, copy it into main.go in a new folder and run it with go run main.go (Go 1.27 or later). How to install Go

Output

[1 2 3 4 5 6]

Next: grouping data with structs.

Previousdefer NextStructs