🎓 A1Learner
🔍

Go Recursion

Recursion is a way of solving a problem where a function calls itself. Each call works on a smaller input than the call before it.

A countdown that calls itself

The countDown function prints its number first. It then calls itself with one less.

package main

import "fmt"

func countDown(n int) {
	if n == 0 {
		return
	}
	fmt.Println(n)
	countDown(n - 1)
}

func main() {
	countDown(3)
}

Factorial by recursion

The factorial of a number is that number times the factorial of one less. The base case gives 1 for zero.

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))
}

Two calls in one return

The fib function adds the results of two smaller calls. Numbers below two are the base case and return as they are.

package main

import "fmt"

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

func main() {
	fmt.Println(fib(10))
}

Example

package main

import "fmt"

func launch(n int) {
	if n == 0 {
		fmt.Println("Liftoff!")
		return
	}
	fmt.Println(n)
	launch(n - 1)
}

func main() {
	launch(3)
}

Key points

  • A recursive function calls itself with a new argument.
  • A base case is the stopping case that returns without another call.
  • Each call should move the input closer to the base case.
  • The calls finish in reverse order as each one returns.

In this example, launch prints 3 and calls itself with 2. The calls print 2 and then 1 in the same way. The call with zero hits the base case and prints the final line instead.

Note

A missing base case makes the calls go on without an end the program can reach.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Go Playground

Exercise

What is the job of the base case in a recursive function?