Recursion

We have seen that functions can call other functions. Recursion means that functions can call themselves. In each consecutive call, the computation done is dependent on the data produced by the previous call.

One good example of recursion is the factorial. Recall that $n!$ (n factorial) is simply the product of all numbers from $1$ to $n$: $$ \begin{equation}\begin{aligned} n!=1\times 2\times 3\times ... \times (n-1) \times n\\ \end{aligned}\end{equation} $$

We can write a function to find the factorial of a number:

package main

import "fmt"

func factorial(n int) int {
	// if the number becomes 1 then stop recursion by returning 1
	if n == 1 {
		return 1
	}
	// return the current number times the factorial of the number minus 1
	return n * factorial(n-1)
}

func main() {
	fmt.Println(factorial(1))
	fmt.Println(factorial(3))
	fmt.Println(factorial(5))
	fmt.Println(factorial(15))
}

Recursion with an anonymous function

We can store a reference to an anonymous function and call it within the function itself:

package main

import "fmt"

func main() {
	var fib func(n int) int

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

	fmt.Println(fib(20))
}

Note the declaration of the fib variable. The name is “fib” and the type is “a function that accepts an integer n and returns an integer” (func (n int) int).