HTML
JAVASCRIPT
CSS
PYTHON
SQL
JAVA
GO
REACT

Go Recursion

What is Recursion?

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem. It continues until a base condition is met, preventing infinite loops. Recursion is useful for problems like factorial computation, Fibonacci sequence generation, and tree traversal.

Syntax of Recursion in Go

A recursive function in Go consists of:

  • A terminating condition that prevents additional recursive calls.
  • A recursive scenario in which the function invokes itself with adjusted parameters.
package main

import "fmt"

// Recursive function example
func recursiveFunction(n int) {
    if n <= 0 { // Base case
        fmt.Println("Recursion ends here")
        return
    }
    fmt.Println("Current value:", n)
    recursiveFunction(n - 1) // Recursive call with decremented value
}

func main() {
    recursiveFunction(5)
}

Output:

Current value: 5  
Current value: 4  
Current value: 3  
Current value: 2  
Current value: 1  
Recursion ends here

Example 1: Factorial using Recursion

Factorial of a number nnn is defined as:

n!=n×(n−1)×(n−2)×...×1
package main

import "fmt"

// Function to compute factorial recursively
func factorial(n int) int {
    if n == 0 {
        return 1 // Base case: 0! is 1
    }
    return n * factorial(n-1) // Recursive case
}

func main() {
    num := 5
    fmt.Printf("Factorial of %d is %d\n", num, factorial(num))
}

Output:

Factorial of 5 is 120

Example 2: Fibonacci Sequence with Recursion

The Fibonacci sequence follows the rule:

F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)

where F(0)=0F(0) = 0F(0)=0 and F(1)=1F(1) = 1F(1)=1.

package main

import "fmt"

// Recursive function to calculate Fibonacci numbers
func fibonacci(n int) int {
    if n <= 1 {
        return n // Base cases: F(0) = 0, F(1) = 1
    }
    return fibonacci(n-1) + fibonacci(n-2) // Recursive case
}

func main() {
    num := 6
    fmt.Printf("Fibonacci number at position %d is %d\n", num, fibonacci(num))
}

Output:

Fibonacci number at position 6 is 8

Example 3: Sum of Digits using Recursion

A function that recursively calculates the sum of digits of a number.

package main

import "fmt"

// Function to compute sum of digits
func sumOfDigits(n int) int {
    if n == 0 {
        return 0 // Base case: if no digits left
    }
    return (n % 10) + sumOfDigits(n/10) // Recursive case
}

func main() {
    num := 1234
    fmt.Printf("Sum of digits of %d is %d\n", num, sumOfDigits(num))
}

Output:

Sum of digits of 1234 is 10

Example 4: Reverse a String Recursively

A function that reverses a string using recursion.

package main

import "fmt"

// Recursive function to reverse a string
func reverseString(s string) string {
    if len(s) == 0 {
        return "" // Base case: empty string
    }
    return string(s[len(s)-1]) + reverseString(s[:len(s)-1]) // Recursive case
}

func main() {
    str := "hello"
    fmt.Printf("Reversed string: %s\n", reverseString(str))
}

Output:

Reversed string: olleh

Key Points to Remember About Recursion in Go

  • 1. Every recursion must have a base condition to prevent infinite loops.
  • 2. Recursive calls consume stack memory, so excessive recursion may cause a stack overflow.
  • 3. Tail recursion is not optimized by Go's compiler, so deep recursion should be avoided in performance-critical applications.
  • 4. Recursion can be replaced with iteration in some cases for better efficiency.
PreviousNext