Recursion in Golang

Recursion is one of the important concepts in programming languages. In this post, we will learn how to use recursion in Go.

What is Recursion?

Recursion happens when a function calls itself, i.e it recurs. When a function inside a program calls itself recursion occurs.

Criteria for Recursion

To be a recursive function it has to fulfill some predefined conditions. These are:

  1. It calls itself.
  2. It has a stopping condition.

Those functions which don’t follow the rule can be called an infinitely recursive function.

Recursion types

There can be two types of recursion as explained above. First is the finite or regular recursion and the other, which is infinite recursion. Let’s see what those are.

1. Finite recursion

Finite recursion or simply recursion is the state of function in which:

  1. The function calls itself.
  2. It stops at the boundary condition.

Below is an example of a finite recursion.

package main

import (
	"fmt"
)

func recurFact(v int) int {
	if (v == 0) { 
		return 1 
	} else { 
		return v * recurFact(v-1) 
	}
}

func main() {
	n := recurFact(10)
	
	fmt.Println(n)         // 3628800
}

2. Infinite recursion

Infinite recursion happens when the second condition is not followed. Or to put it simply, the function doesn’t stop calling itself. Here is an infinite recursion in action.

package main

import (
	"fmt"
)

func recurse() {
	fmt.Println("Endless!")
	recurse()
}

func main() {
	// recurse() // infinite call
}

Recursion methods

Recursion has different methods or order of calling itself by which it can be classified into two different types. The first one being regular while the second one is tail-recursive. Let’s have a look at each one of them.

1. Regular recursion

Regular recursion is when calling itself does not finish the calculation immediately instead it passes it down the hierarchy. Below is an example showing that.

package main

import (
	"fmt"
)

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

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

2. Tail-recursion

Tail recursion happens when a function calling itself calculates the value and sends it down the hierarchy. Here is an example of a tail-recursion.

package main

import (
	"fmt"
)

func f(v int) {
	if(v == 0) {
		fmt.Println("Zero")
		return
	} else {
		fmt.Println(v)
		f(v-1)               // tail-recursive call
	}
}

func main() {
	f(5)
	
	// output:
	// 5
	// 4
	// 3
	// 2
	// 1
	// Zero
}

Tail-recursion benefits

The tail-calls are beneficial in an aspect that it is optimized by compilers in many cases. So, it is almost always faster than a normal recursive call.

Function types

Both types of functions can be used for recursion. The regular ones and the anonymous function.

1. Regular function

Here is a regular function showing recursive nature.

package main

import (
	"fmt"
)

func f(v int) {
	if(v == 0) {
		return
	} else {
		fmt.Println(v)
		f(v-1)       
	}
}

func main() {
	f(5)
	
	// output:
	// 5
	// 4
	// 3
	// 2
	// 1
	// Zero
}

2. Anonymous function

Anonymous functions can be recursive as well. Here is an anonymous function showing recursion.

package main

import (
	"fmt"
)

func main() {
	var f func(int)
	
	f = func(v int) {
		if(v == 5) {
			fmt.Println("Done")
			return
		} else {
			fmt.Println(v)
			f(v-1)
		}
	}
	
	f(9)

	// Output: 
	// 9
	// 8
	// 7
	// 6
	// Done
}