Go - Recursion

---

---

Recursion is the process of repeating items in a self-similar way. The same concept applies in programming languages as well. If a program allows to call a function inside the same function,

func recursion() {
   recursion() /* function calls itself */
}
func main() {
   recursion()
}

The Go programming language supports recursion. That is, it allows a function to call itself. But while using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go on to become an infinite loop.

Examples of Recursion in Go

Recursive functions are very useful to solve many mathematical problems such as calculating factorial of a number, generating a Fibonacci series, etc.

Example 1: Calculating Factorial Using Recursion in Go

The following example calculates the factorial of a given number using a recursive function −

package main

import "fmt"

func factorial(i int)int {
   if(i <= 1) {
      return 1
   }
   return i * factorial(i - 1)
}
func main() { 
   var i int = 15
   fmt.Printf("Factorial of %d is %d", i, factorial(i))
}

When the above code is compiled and executed, it produces the following result −

Factorial of 15 is 1307674368000

Example 2: Fibonacci Series Using Recursion in Go

The following example shows how to generate a Fibonacci series of a given number using a recursive function −

package main

import "fmt"

func fibonaci(i int) (ret int) {
   if i == 0 {
      return 0
   }
   if i == 1 {
      return 1
   }
   return fibonaci(i-1) + fibonaci(i-2)
}
func main() {
   var i int
   for i = 0; i < 10; i++ {
      fmt.Printf("%d ", fibonaci(i))
   }
}

When the above code is compiled and executed, it produces the following result −

0 1 1 2 3 5 8 13 21 34 

Components of Recursion in Go

To understand more about the Recursive Algorithm, Let's learn about the two components named as Base Case, Recursive Case as below −

• Base Case: The base case in a recursive algorithm is a condition or set of conditions that stop the recursion.
• Recursive Case: The recursive case in a recursive algorithm is the part of the function where the function calls by itself.

To understand the above two cases better imagine you are standing in front of a staircase, and you want to reach the top. You can either jump directly to the top is called base case and If you are on the last step, or taking one step at a time and then solving the problem for the remaining steps is called recursive case.

Let's print the sum of natural numbers using recursion. Formulate a function to calculate the summation of all natural numbers from 1 to n as:

F(n) = 1 + 2 + 3 + 4 + + (n-2) + (n-1) + n

Let's have an idea about the concept of base case and recursive case through diagram −

Types of Recursion in Go

In Golang, recursion is a common technique used for solving problems where a function calls by itself as a part of its processing.

There are different types of recursion based on how the function calls itself and processes the data.

1. Direct Recursion

The direct recursion is a straightforward form. It occurs when a function calls by itself within its own body.

func factorial(n int) int {
   // Base case: If n is 0, return 1.
   if n == 0 {
       return 1
   }
   // Recursive case: Multiply n by the result of factorial(n-1).
   return n * factorial(n-1)
}

Example

The function factorial calls itself directly to calculate the factorial of a number n. The base case (if n == 0) ensures that the recursion stops when n reaches 0. Each recursive call reduces the problem size (n-1) until the base case is met.

package main
import "fmt"

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

func main() {
   n := 5
   fmt.Println("Factorial of", n, "is", factorial(n))
}

Output

Run the code and check its output −

Factorial of 5 is 120

2. Indirect Recursion

The indirect recursion occurs when a function calls another function, which later calls the first function again. It involve two or more functions that call each other in a specific order.

func funcA(n int) {
    if n > 0 {
        funcB(n - 1)
    }
}
func funcB(n int) {
    if n > 0 {
        funcA(n - 1)
    }
}

Example

In this example, funcA calls funcB if n is greater than 0 and funcB calls funcA if n is greater than 0. The process continues until the base condition (n > 0) is no longer satisfied.

package main
import "fmt"

func funcA(n int) {
    if n > 0 {
        fmt.Println("funcA:", n)
        funcB(n - 1)
    }
}

func funcB(n int) {
    if n > 0 {
        fmt.Println("funcB:", n)
        funcA(n - 1)
    }
}

func main() {
    funcA(3)
}

Output

Run the code and check its output −

funcA: 3
funcB: 2
funcA: 1

3. Tail Recursion

The tail recursion is a special form of recursion where the recursive call is the last operation in the function. This means that there are no other additional calculations or operations after the recursive call.

func tailFactorial(n int, accumulator int) int {
   // Base case
   if n == 0 {
      return accumulator
   }
   // Recursive call
   return tailFactorial(n-1, n*accumulator)
}

Example

The function stops when n is 0 and returns the value of the accumulator(base case) and the recursive call is the last operation, and it passes the next value of n and the updated value of the accumulator(recursive case).

package main
import "fmt"

func tailFactorial(n int, accumulator int) int {
   if n == 0 {
      return accumulator
   }
   return tailFactorial(n-1, n*accumulator)
}

func main() {
   n := 5
   result := tailFactorial(n, 1)
   fmt.Println("Factorial of", n, "is", result)
}

Output

Run the code and check its output −

Factorial of 5 is 120

4. Head Recursion

The head recursion occurs when a function makes its recursive call at the beginning (or "head") of the function, before performing any other operations. This means the recursive call is made first, and other operations are performed after the recursive call.

func headRecursion(n int) int {
    // Base case
    if n <= 0 {
        return 0
    }
	// Recursive call
    return n + headRecursion(n-1)
}

Example

In this example, the function stops when n is 0(base case) and the recursive call headSum(n-1) is made first before any other operations(recursive case).

package main
import "fmt"

func headSum(n int) int {
    if n == 0 {
        return 0
    }
    result := headSum(n-1)
    return result + n
}

func main() {
    n := 5
    result := headSum(n)
    fmt.Println("Sum of natural numbers up to", n, "is", result)
}

Output

Run the code and check its output −

Sum of natural numbers up to 5 is 15

5. Mutual Recursion

The mutual recursion occurs when two or more functions call each other in a cyclic manner, creating a loop of function calls between the function involved. It can involve any number of functions, but the simplest case involves two functions calling each other.

func isEven(n int) bool {
   if n == 0 {
      return true
   }
   return isOdd(n - 1)
}

func isOdd(n int) bool {
   if n == 0 {
      return false
   }
   return isEven(n - 1)
}

Example

In this example, To determine if a number n is even, isEven checks if n1 is odd and next to determine if a number n is odd, isOdd checks if n1 is even.This mutual calling continues until n reaches 0.

package main
import "fmt"

func isEven(n int) bool {
   if n == 0 {
      return true
   }
   return isOdd(n - 1)
}

func isOdd(n int) bool {
   if n == 0 {
      return false
   }
   return isEven(n - 1)
}

func main() {
   n := 5
   fmt.Println(n, "is even:", isEven(n))
   fmt.Println(n, "is odd:", isOdd(n))
}

Output

Run the code and check its output −

5 is even: false
5 is odd: true

6. Infinite Recursion

The infinite recursion happens when a recursive function doesn't have a proper base case to stop the recursion. This results in the function calling itself endlessly, causing a stack overflow error due to continuous function calls.

func infiniteRecursion() {
   // No base case
   infiniteRecursion()
}

Example

In this example, the function infiniteRecursion does not have a base case to stop the recursion. so, it leads to infinite recursion itself without stopping.

package main
import "fmt"

func infiniteRecursion() {
   fmt.Println("This will run indefinitely...")
   infiniteRecursion()
}

func main() {
   infiniteRecursion()
}

Output

Run the code and check its output −

This will run indefinitely...
This will run indefinitely...
This will run indefinitely...
This will run indefinitely...

7. Nested Recursion

The nested recursion occurs when a function's recursive call itself contains another recursive call as a parameter means one recursive call is nested inside another.

// Nested Recursive Function
func nestedRecursion(n int) int {
   if n > 100 {
      return n - 10
   }
   return nestedRecursion(nestedRecursion(n + 11))
}

Example

In this example, nestedRecursion calls itself with an argument that result of another recursive call, creating a complex tree of calls. The recursion continues until the innermost call meets the base case.

package main
import "fmt"

func nestedRecursion(n int) int {
   if n > 100 {
      return n - 10
   }
   return nestedRecursion(nestedRecursion(n + 11))
}

func main() {
   n := 64
   result := nestedRecursion(n)
   fmt.Println("Nested recursion for", n, "is", result)
}

Output

Run the code and check its output −

Nested recursion for 64 is 91

8. Anonymous Function Recursion

The anonymous function recursion happens when an anonymous function (lambda function) calls itself. These functions defined without a name that can be assigned to variables or used as arguments and can recursively call themselves.

var factorial func(int) int
factorial = func(n int) int {
   // Base case
   if n == 0 {
      return 1
   }
   // Recursive Case
   return n * factorial(n-1)
}

Example

In this example, the anonymous function assigned to the factorial variable calls itself to calculate the factorial of a number. This demonstrates how anonymous functions can be used for recursive operations.

package main

import "fmt"

func main() {
   var factorial func(int) int
   factorial = func(n int) int {
      if n == 0 {
         return 1
      }
      return n * factorial(n-1)
   }
   
   n := 5
   result := factorial(n)
   fmt.Println("Factorial of", n, "is", result)
}

Output

Run the code and check its output −

Factorial of 5 is 120