Learn/Go/11. Recursion
Lesson 11 of 15
Sign in

Go, lesson 11

Recursion

A recursive function is one that calls itself. That sounds circular, but it is a natural way to solve problems that contain smaller copies of themselves: a folder holds folders, a sentence can contain a sentence, and the sum of a list is the first item plus the sum of the rest.

The two parts

Every recursive function needs:

  1. A base case: an input small enough to answer directly, without recursing.
  2. A recursive case: break the problem into a smaller version, call yourself on it, and combine the answer.

The classic example is factorial, where 5! = 5 × 4 × 3 × 2 × 1:

Trace factorial(3): it needs 3 * factorial(2), which needs 2 * factorial(1), which returns 1. The calls then finish in reverse order: 2 * 1 = 2, then .

2 exercises to try what you just read.

Exercise 1

Digital root

Press Ctrl Enter or Check to test your code.

Exercise 2

Tower of Hanoi

Press Ctrl Enter or Check to test your code.

3 * 2 = 6

Each call gets its own copy of n. Go keeps these on the call stack, a pile of unfinished calls waiting for answers. Forget the base case, or fail to make the input smaller, and the pile grows until the program crashes with a stack overflow. Go's stack grows quite large, so this usually shows up as a long hang followed by a crash rather than an immediate error.

Recursion on slices and strings

Slicing makes "the rest" easy to express:

nums[1:] does not copy anything; it is a new view on the same storage, so this is cheap.

Branching recursion

Some problems split into two or more smaller problems. Counting the ways to climb stairs taking 1 or 2 steps at a time is one:

This is elegant but slow for big n, because it solves the same sub-problems again and again. The fix is memoisation: remember answers in a map and reuse them.

Recursion or a loop?

Anything recursive can be written with a loop, and Go has no tail-call optimisation, so a simple countdown is better as a for loop. Recursion shines when the data is shaped like a tree, or when the problem naturally branches: generating combinations, exploring a maze, solving puzzles like the Tower of Hanoi. Choose whichever makes the code clearer.

A helpful habit when writing a recursive function: trust that the recursive call works for the smaller input, and only think about how to use its answer. This "leap of faith" is what makes recursion feel simple.

Further reading

  • A Tour of Go: Functions
  • The Go spec: Function declarations
  • Effective Go: Slices

The digital root of a number comes from adding up its digits, then adding up the digits of that result, and so on until a single digit remains. For 9875: 9+8+7+5 = 29, 2+9 = 11, 1+1 = 2.

Write a recursive function digitSum(n int) int that adds the digits of n (use n % 10 for the last digit and n / 10 for the rest), and a recursive function digitalRoot(n int) int that uses it. Read one non-negative integer and print its digital root.

Sample input:

Sample output:

Three pegs are labelled A, B and C. Peg A holds n disks, largest at the bottom. Move all disks to peg C, one at a time, never putting a larger disk on a smaller one.

The recursive plan for moving n disks from from to to using spare: move n-1 disks from from to spare, move disk n from from to to, then move the n-1 disks from spare to to.

Read n (0 to 10) and print every move as disk <d>: <from> -> <to>, then a final line moves: <total>.

Sample input:

Sample output:

func factorial(n int) int {
	if n <= 1 {
		return 1 // base case
	}
	return n * factorial(n-1) // smaller problem
}
func sum(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	return nums[0] + sum(nums[1:])
}
func ways(n int) int {
	if n <= 1 {
		return 1
	}
	return ways(n-1) + ways(n-2)
}
var memo = map[int]int{}

func fastWays(n int) int {
	if n <= 1 {
		return 1
	}
	if v, ok := memo[n]; ok {
		return v
	}
	memo[n] = fastWays(n-1) + fastWays(n-2)
	return memo[n]
}
9875
2
2
disk 1: A -> B
disk 2: A -> C
disk 1: B -> C
moves: 3