Go Recursion

In computer programming, a recursive function calls itself. For example,

func recurse() {
  … …
  … …
  recurse()
}

Here, the recurse() function includes the function call within its body. Hence, it is a Go recursive function and this technique is called recursion.

Before you learn about recursion, make sure to know Go Functions.

Example: Recursion in Golang

package main
import "fmt"

func countDown(number int) {

  // display the number
  fmt.Println(number)

  // recursive call by decreasing number
  countDown(number - 1)

  }

func main() {
  countDown(3)
}

Output

Countdown Starts:
3
2
1
0
-1
…
…

In the above example, we have created a function named countDown(). Note that we have added the function call inside the function.

countDown(number - 1)

Here, this is a recursive function call and we are decreasing the value of number in each call.

However, this function will be executed infinitely because we have added the function call directly within the function

To avoid infinite recursion, we use conditional statements and only call the function if the condition is met.

Recursive Function with conditional statement

In this example, we will use an if...else statement to prevent the infinite recursion.

// Program to end the recursive function using if…else

package main
import "fmt"

func countDown(number int) {

  if number > 0 {
    fmt.Println(number)

    // recursive call
    countDown(number - 1)
  } else {
    // ends the recursive function 
    fmt.Println("Countdown Stops")
  }

 }

func main() {
  countDown(3)
}

Output

Countdown Starts
3
Countdown Starts
2
Countdown Starts
1
Countdown Starts
Countdown Stops

In the above example, we have added the recursive call inside the if statement.

if number > 0 {
  fmt.Println(number)

  // recursive call
  countDown(number - 1)
}

Here, we are calling the function only if the number is greater than 0.

If the number is not greater than 0, the recursion ends. This is called the stopping condition.

Working of the program

Example: Go program to calculate the sum of positive numbers

package main
import "fmt"

func sum(number int) int {

  // condition to break recursion
  if number == 0 {
    return 0
  } else {
    return number + sum(number-1)
  }
}

func main() {
  var num = 50

  // function call
  var result = sum(num)

  fmt.Println("Sum:", result)
}

Output

Sum: 1275

In the above example, we have created a recursive function named sum() that calls itself if the value of number is not equal to 0.

return number + sum(number - 1)

In each iteration, we are calling the function by decreasing the value of number by 1.

Here's how the program works:

• In first call, the value of number is 50 which is not equal to 0. So, the else block is executed which returns 50 + sum(49).
• Again, 49 is not equal to 0, so return 49 + sum(48) is executed.
• This process continues until number becomes 0. When number is 0, return 0 is executed and it is added to the other values.
• Hence, finally, 50 + 49 + 48 + ...... + 0 is computed and returned to the main() function.

Factorial of a number using Go Recursion

package main
import "fmt"

func factorial (num int) int {

  // condition to break recursion
  if num == 0 {
    return 1
  } else {
    // condition for recursion call
    return num * factorial (num-1)
   }
}

func main() {
  var number = 3
  
  // function call
  var result = factorial (number)

  fmt.Println("The factorial of 3 is", result)
}

Output

The factorial of 3 is 6

In the above example, we have created a recursive function named factorial() that calls itself if the value of num is not equal to 0.

return num * factorial(num - 1)

In each call, we are decreasing the value of num by 1.

Here's how the program works: