Go Recursion

Introduction

Recursion is a programming technique where a function calls itself to solve a problem. Recursive functions can be elegant and easy to understand when used appropriately. They are particularly useful for problems that can be broken down into smaller, similar sub-problems. In this chapter, you will learn the basics of recursion in Go, including examples to illustrate how to write and use recursive functions effectively.

Basics of Recursion

A recursive function must have two main components:

1. Base Case: A condition under which the function stops calling itself, preventing infinite recursion.
2. Recursive Case: The part of the function where it calls itself with modified arguments.

Examples

Factorial of a Number

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It can be defined recursively as:

• factorial(0) = 1
• factorial(n) = n * factorial(n-1) for n > 0

Example:

package main

import "fmt"

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

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

Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. It can be defined recursively as:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n-1) + fib(n-2) for n > 1

Example:

package main

import "fmt"

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

func main() {
    fmt.Println("Fibonacci of 7:", fib(7)) // Output: Fibonacci of 7: 13
}

Recursive Sum of an Array

A function to find the sum of all elements in an array can also be defined recursively.

Example:

package main

import "fmt"

func sumArray(arr []int, n int) int {
    if n <= 0 {
        return 0 // Base case
    }
    return arr[n-1] + sumArray(arr, n-1) // Recursive case
}

func main() {
    arr := []int{1, 2, 3, 4, 5}
    fmt.Println("Sum of array:", sumArray(arr, len(arr))) // Output: Sum of array: 15
}

Understanding Recursion Depth and Base Case

It’s important to ensure that the base case will be reached to avoid infinite recursion, which can lead to a stack overflow.

Example of Infinite Recursion:

package main

import "fmt"

func infiniteRecursion() {
    fmt.Println("Infinite recursion")
    infiniteRecursion() // No base case, this will cause a stack overflow
}

func main() {
    // infiniteRecursion() // Uncommenting this will cause a stack overflow
}

Optimizing Recursion

Memoization

Recursive functions can be inefficient if they repeatedly solve the same sub-problems. Memoization is a technique to store previously computed results to avoid redundant calculations.

Example of Fibonacci with Memoization:

package main

import "fmt"

var memo = map[int]int{}

func fibMemo(n int) int {
    if n <= 1 {
        return n // Base case
    }
    if result, exists := memo[n]; exists {
        return result // Return cached result
    }
    memo[n] = fibMemo(n-1) + fibMemo(n-2) // Compute and store result
    return memo[n]
}

func main() {
    fmt.Println("Fibonacci of 7:", fibMemo(7)) // Output: Fibonacci of 7: 13
}

Conclusion

Recursion is a powerful technique in Go for solving problems that can be divided into smaller sub-problems. Understanding the base case and recursive case is crucial for writing effective recursive functions. While recursion can lead to elegant solutions, it’s essential to ensure that the base case is reached to prevent infinite recursion. Additionally, techniques like memoization can optimize recursive functions, making them more efficient.