Recursion functions are supported in Go. While recursive functions are not unique to go, they are useful for solving special kinds of problems.

Download PDF

Example

Introduction

In the previous articles we have discussed functions. What makes a function recursive?

A function is recursive if it:

  1. Calls itself
  2. Reaches the stop condition

The function below is not a recursive function:

func hello() {
fmt.Println("hello world")
hello()
}

Because it calls itself (1), but it doesn’t have a stop condition (2).

But the function below is a recursive function. It matches both conditions;

func countdown(x int) int {
if x == 0 {
return 0
}
fmt.Println(x)
return countdown(x - 1)
}

Factorial function

In the example we create a factorial function and make it calculate 3!.

Here is the recursive function:

func factorial(x uint) uint {
if x == 0 {
return 1
}
return x * factorial(x-1)
}

If called, the function calls itself:

return x * factorial(x-1)

And it has a stop condition x == 0. After which it ends the function execution.

Full code below:

package main

import "fmt"

func factorial(x uint) uint {
if x == 0 {
return 1
}
return x * factorial(x-1)
}

func main(){
x := factorial(3)
fmt.Println(x)
}

Exercises

  • When is a function recursive?
  • Can a recursive function call non-recursive functions?