Go Recursion

2022-11-06T19:07:23.069Z

In Programming, Recursion is a programming technique where the function or an algorithm calls itself one or more times until a specific condition is met.

Go supports recursion. Any function that calls itself is called as a recursive function. For Example:

func sum() {
	// function body
	//...
	sum()
}

In the above example, we have a function named sum(), and inside the function body, we call the sum() method itself.

In mathematics, it is common to define functions recursively. For example, the factorial function is defined as:

0! = 1
for all n > 0, n! = n * (n - 1)!

Similarly, the Fibonacci sequence is defined as:

F(0) = 0
F(1) = 1
for all n > 1, F(n) = F(n - 1) + F(n - 2)

What they have in common is that they are defined in terms of themselves. And you can do similar things in Go.

Recursive factorial in Go

Let's start with the factorial function. We can define it as:

package main

import "fmt"

func factorial(n int) int {
	if n == 0 {
		return 1
	}
	return n * factorial(n-1)
}

func main() {
	fmt.Print(factorial(5))
}

Output

This is very similar to the mathematical definition.

Note: The if statement is fundamental to the definition, and it acts as a stop condition; otherwise, the function would never stop and goes to infinity:

factorial(1) would call factorial(0),
factorial(0) would call factorial(-1),
factorial(-1) would call factorial(-2),
ad infinitum.

It is called a base case.

Recursive Fibonacci in Go

If you want to use a recursive function to compute the nth Fibonacci number, you need a base case for n == 0 and n == 1:

package main

import "fmt"

func fibonacci(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

func main() {
	fmt.Print(fibonacci(15))
}

Output

But this is not efficient at all. Let's say if we need to find fibonacci of 5

fibonacci(5) calls fibonacci(4) and fibonacci(3),
- fibonacci(4) calls fibonacci(3) and fibonacci(2),
  - fibonacci(3) calls fibonacci(2) and fibonacci(1),
    - fibonacci(2) calls fibonacci(1) and fibonacci(0),
  - fibonacci(2) calls fibonacci(1) and fibonacci(0),
- fibonacci(3) calls fibonacci(2) and fibonacci(1),
  - etc.

This is a case of a double recursion, which leads to exponential complexity. A better way is to use a for loop:

func fibonacci(n int) int {
	x, y := 0, 1
	for i := 0; i < n; i++ {
		x, y = y, x+y
	}
	return x
}

So be careful when you choose recursion, it can be slow if you don't use it properly. The rule of thumb is to avoid recursive functions when they are multiple calls to the function itself.