GO Tutorial

Recursion in Go

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem until it reaches a base condition. Go supports recursion naturally, and it’s useful for tasks like factorial calculation, tree traversal, and more.

How Recursion Works

A recursive function has two main parts:

• Base Case: Stops the recursion to prevent infinite calls.
• Recursive Case: The function calls itself with modified arguments, moving towards the base case.

Example: Factorial Using Recursion

func factorial(n int) int {
    if n == 0 {
        return 1               // Base case: factorial of 0 is 1
    }
    return n * factorial(n-1)  // Recursive call
}

func main() {
    fmt.Println("Factorial of 5:", factorial(5)) // Output: 120
}
  

Example: Fibonacci Sequence Using Recursion

func fibonacci(n int) int {
    if n <= 1 {
        return n  // Base cases: fib(0)=0, fib(1)=1
    }
    return fibonacci(n-1) + fibonacci(n-2)  // Recursive calls
}

func main() {
    for i := 0; i < 10; i++ {
        fmt.Printf("%d ", fibonacci(i))
    }
    // Output: 0 1 1 2 3 5 8 13 21 34
}
  

Things to Remember

• Always define a base case to avoid infinite recursion and stack overflow.
• Each recursive call uses its own stack frame, so very deep recursion may cause performance or memory issues.
• In some cases, iteration (loops) can be more efficient than recursion.

Summary

Recursion in Go is a powerful tool to solve problems by breaking them down into smaller, similar subproblems. Proper use of base cases is essential to avoid infinite loops.