Recursion

A function can call other functions. It can also call itself. This is called recursion. It helps when a problem can be split into a smaller copy of the same problem.

Take the sum 1 + 2 + ... + n. The sum up to 4 is 4 plus the sum up to 3. The sum up to 3 is 3 plus the sum up to 2. Each step is the same problem with a smaller number. It stops at 1, because the sum up to 1 is just 1.

package main

import "fmt"

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

func main() {
	fmt.Println(sumTo(4))
	fmt.Println(sumTo(100))
}

Output:

10
5050

A recursive function has two parts:

  • The base case, if n == 1 { return 1 }, answers the smallest problem directly, with no new call. This is what stops the recursion.
  • The recursive case, return n + sumTo(n-1), calls the same function with a smaller number.

Here is how sumTo(4) works out. Each call waits for the smaller call to return, then adds its own n:

sumTo(4) = 4 + sumTo(3)
         = 4 + 3 + sumTo(2)
         = 4 + 3 + 2 + sumTo(1)
         = 4 + 3 + 2 + 1
         = 10

Sum of digits

Recursion works well with the / and % operators. For a whole number n, n % 10 is its last digit, and n / 10 is the number without its last digit. So the digit sum of 472 is 2 plus the digit sum of 47. The base case is a number with one digit, whose digit sum is the number itself:

package main

import "fmt"

func digitSum(n int) int {
	if n < 10 {
		return n
	}
	return n%10 + digitSum(n/10)
}

func main() {
	fmt.Println(digitSum(472))
}

Output:

13

4 + 7 + 2 is 13.

Forgetting the base case

Without a base case, the function never stops calling itself. Every call needs a little memory to keep its own n while it waits. Here the calls go on until the program runs out of memory and crashes:

package main

import "fmt"

func sumTo(n int) int {
	return n + sumTo(n-1)
}

func main() {
	fmt.Println(sumTo(3))
}

Output:

runtime: out of memory: cannot allocate 268435456-byte block (138084352 in use)
fatal error: out of memory

After these two lines, Go prints a very long report that lists the calls that were still waiting. It is cut here.

The base case must also be reachable. Each call has to move closer to it. With the first version of sumTo, a call like sumTo(0) would count down 0, -1, -2 and so on, and never reach 1.

Recursion or a loop?

sumTo can also be written with a loop:

total := 0
for i := 1; i <= 100; i++ {
	total += i
}
fmt.Println(total)

Output:

5050

For a simple count like this, the loop is easier to read, and it does not use memory for waiting calls. Recursion is the better choice when a problem splits into smaller copies of itself in a natural way. You will meet many such problems in coding interviews, for example when you work with trees.

In the exercise, complete factorial. The factorial of n is 1 * 2 * ... * n, and the factorial of 0 is 1, which is your base case.