Recursion and the stack

A recursive function calls itself with a smaller argument and stops at a base case. Go puts no limit on the shape of that call: there is no special syntax, no tail-call optimisation, and no fixed stack to overflow at a modest depth, because a goroutine starts with a small stack and grows it as needed. The functions lesson showed a function value; this one shows a function that is its own caller.

A base case and a step

The base case returns without calling again, and the step makes the argument strictly smaller. Each call has its own copy of n and its own return address, so the loop version and the recursive one compute the same number with different memory: the loop keeps one frame, the recursion keeps n of them until it unwinds. For factorial the loop is clearer; for a tree the recursion is.

package main import "fmt" func factorialLoop(n int) int { result := 1 for i := 2; i <= n; i++ { result *= i } return result } func factorial(n int) int { if n <= 1 { return 1 } return n * factorial(n-1) } func main() { for _, n := range []int{0, 1, 5, 10} { fmt.Printf("%d! loop %d recursive %d\n", n, factorialLoop(n), factorial(n)) } }

go run fact.go

0! loop 1 recursive 1
1! loop 1 recursive 1
5! loop 120 recursive 120
10! loop 3628800 recursive 3628800

The four pairs agree. The recursive version reads as the mathematical definition, and the compiler cannot turn the n * factorial(n-1) call into a jump because the multiply has to happen after the call returns: Go does not do tail-call optimisation even for the shape that would allow it.

Recursion over a tree

A tree is the data structure recursion was made for: a node holds a value and pointers to smaller trees, and the base case is the nil pointer. The sum and the depth are two lines each, and an iterative version needs an explicit stack or a queue and a loop that is longer than the problem.

package main import "fmt" type node struct { value int left *node right *node } func sum(n *node) int { if n == nil { return 0 } return n.value + sum(n.left) + sum(n.right) } func depth(n *node) int { if n == nil { return 0 } return 1 + max(depth(n.left), depth(n.right)) } func main() { tree := &node{1, &node{2, &node{4, nil, nil}, nil}, &node{3, nil, &node{5, nil, nil}}, } fmt.Println("sum:", sum(tree)) fmt.Println("depth:", depth(tree)) }

go run tree.go

sum: 15
depth: 3

The sum is 15 and the depth is 3, counted by the longest path from the root to a leaf. Every call on a nil child returns immediately, so the number of calls is one per node plus one per empty child: the base case is part of the algorithm, not an afterthought.

Memoisation makes it fast

The naive fibonacci calls itself twice per step, which is exponential: fib(40) is about three hundred million calls. A map from n to the answer turns the second call for the same n into a lookup, and the same program becomes linear. The map is the memo, and the closure that reads and writes it is the simplest way to keep it private.

package main import "fmt" func main() { memo := map[int]int{0: 0, 1: 1} calls := 0 var fib func(int) int fib = func(n int) int { calls++ if v, ok := memo[n]; ok { return v } v := fib(n-1) + fib(n-2) memo[n] = v return v } fmt.Println("fib(40):", fib(40), "calls:", calls) fmt.Println("fib(30) again:", fib(30), "calls:", calls) }

go run memo.go

fib(40): 102334155 calls: 79
fib(30) again: 832040 calls: 80

Forty-one calls produced fib(40) instead of the millions, and the second query added none because the answer was already there. A memo has to be safe for concurrent use if the function is shared, which means a mutex or sync.Map; here the function never leaves main.

The stack grows

A goroutine starts with an eight-kilobyte stack and doubles it when a call would overflow, copying the frames to the new one. A recursion a hundred thousand deep therefore works, which it would not on a fixed one-megabyte thread stack. The price is that the stack is not contiguous and a pointer into it is not stable, which is why Go has no pointer arithmetic and why the runtime can move a stack.

package main import "fmt" func countdown(n int) int { if n == 0 { return 0 } return 1 + countdown(n-1) } func main() { fmt.Println("depth 100000:", countdown(100000)) sum := 0 var add func(int) add = func(n int) { if n == 0 { return } sum += n add(n - 1) } add(1000) fmt.Println("sum of 1..1000:", sum) }

go run deep.go

depth 100000: 100000
sum of 1..1000: 500500

The countdown of 100000 returned, and the summing closure reached 500500. Growth is not free: the runtime copies the stack, so a very deep recursion costs time and memory, and a runaway recursion eventually hits the one-gigabyte limit and dies with goroutine stack exceeds 1000000000-byte limit.

Exercises

  1. Write a recursive function that reverses a string by slicing off the first rune, and the same function with a loop over indexes. Which one allocates?
  2. Add a memo to the tree sum that remembers subtree results. Does the tree have the repeated subproblems that make a memo worth it?
  3. Increase the countdown to ten million and time it. At what depth does the stack growth become noticeable, and what does the runtime do when the limit is reached?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What must every recursive function have?

    Answer

    A base case that returns without calling itself

    Without a base case the recursion never stops, whatever the language does with the stack.

  2. What does this program print for 5? package main import "fmt" func factorialLoop(n int) int { result := 1 for i := 2; i <= n; i++ { result *= i } return result } func factorial(n int) int { if n <= 1 { return 1 } return n * factorial(n-1) } func main() { for _, n := range []int{0, 1, 5, 10} { fmt.Printf("%d! loop %d recursive %d\n", n, factorialLoop(n), factorial(n)) } }

    Answer

    0! loop 1 recursive 1 / 1! loop 1 recursive 1 / 5! loop 120 recursive 120 / 10! loop 3628800 recursive 3628800

    Both versions compute 120, the loop from 2 upwards and the recursion from 5 downwards.

  3. Does Go optimise a tail call into a jump?

    Answer

    No

    Go has no tail-call optimisation, so a tail-recursive function still grows the stack.

  4. What does this program print? package main import "fmt" type node struct { value int left *node right *node } func sum(n *node) int { if n == nil { return 0 } return n.value + sum(n.left) + sum(n.right) } func depth(n *node) int { if n == nil { return 0 } return 1 + max(depth(n.left), depth(n.right)) } func main() { tree := &node{1, &node{2, &node{4, nil, nil}, nil}, &node{3, nil, &node{5, nil, nil}}, } fmt.Println("sum:", sum(tree)) fmt.Println("depth:", depth(tree)) }

    Answer

    sum: 15 / depth: 3

    The five values add to 15 and the longest path from the root has three nodes.

  5. What does memoisation change about a recursive function?

    Answer

    It turns repeated subproblems into lookups

    A memo pays off only when the same subproblem is reached more than once.

  6. What does the second line of this program print? package main import "fmt" func main() { memo := map[int]int{0: 0, 1: 1} calls := 0 var fib func(int) int fib = func(n int) int { calls++ if v, ok := memo[n]; ok { return v } v := fib(n-1) + fib(n-2) memo[n] = v return v } fmt.Println("fib(40):", fib(40), "calls:", calls) fmt.Println("fib(30) again:", fib(30), "calls:", calls) }

    Answer

    fib(40): 102334155 calls: 79 / fib(30) again: 832040 calls: 80

    Every fib up to 40 was computed once, so the second query needed no new calls.

  7. How large is the stack a goroutine starts with?

    Answer

    Eight kilobytes, and it grows

    The small starting stack is why a program can start many goroutines; growth keeps recursion safe.

  8. What does this program print? package main import "fmt" func countdown(n int) int { if n == 0 { return 0 } return 1 + countdown(n-1) } func main() { fmt.Println("depth 100000:", countdown(100000)) sum := 0 var add func(int) add = func(n int) { if n == 0 { return } sum += n add(n - 1) } add(1000) fmt.Println("sum of 1..1000:", sum) }

    Answer

    depth 100000: 100000 / sum of 1..1000: 500500

    The countdown returns the number of steps, and the closure adds 1 to 1000.

  9. Why is recursion the natural fit for a tree?

    Answer

    The data is defined in terms of smaller copies of itself

    A node holds smaller trees, so a function over a tree calls itself on them.

  10. What happens when a recursion exceeds the stack limit?

    Answer

    The runtime prints a stack overflow and the program dies

    Growth has a bound; past it the goroutine stack exceeds its limit and the process exits.

The code on this page was run with go 1.26.10 on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev

Banner image