Recursion

Next: Pointers

Recursion is a technique where a function calls itself to solve a problem by breaking it down into smaller subproblems. Go supports recursive functions naturally, making it useful for problems that have a recursive structure.

💡 Key Points

Recursion involves a function calling itself to solve smaller instances of a problem
Must have a base case to prevent infinite recursion
Each recursive call should make progress toward the base case
Go doesn't optimize tail recursion - consider iterative alternatives for deep recursion
Stack overflow can occur with too many recursive calls
Memoization can dramatically improve performance for overlapping subproblems
Natural fit for tree/graph traversal, divide-and-conquer algorithms
Can be less efficient than iteration due to function call overhead

Classic Recursion: Factorial

The factorial function is a classic example of recursion. It calculates n! = n * (n-1) * ... * 1:

package main

import "fmt"

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

func main() {
    fmt.Println("5! =", factorial(5))
    fmt.Println("7! =", factorial(7))
    fmt.Println("10! =", factorial(10))
}

Output:

5! = 120
7! = 5040
10! = 3628800

Fibonacci Sequence

Another classic recursive example is calculating Fibonacci numbers:

package main

import "fmt"

// Recursive Fibonacci function
func fibonacci(n int) int {
    // Base cases
    if n <= 1 {
        return n
    }
    // Recursive case: fib(n) = fib(n-1) + fib(n-2)
    return fibonacci(n-1) + fibonacci(n-2)
}

// Efficient version with memoization
func fibMemo(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
    return memo[n]
}

func main() {
    fmt.Println("Fibonacci sequence:")
    for i := 0; i < 10; i++ {
        fmt.Printf("fib(%d) = %d\n", i, fibonacci(i))
    }
    
    // Using memoization for efficiency
    memo := make(map[int]int)
    fmt.Println("\nfib(40) with memo:", fibMemo(40, memo))
}

Output:

Fibonacci sequence:
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34

fib(40) with memo: 102334155

Recursion Components

Component	Description	Example
Base Case	Condition that stops recursion	`if n == 0 { return 1 }`
Recursive Case	Function calls itself with modified args	`return n * factorial(n-1)`
Progress	Each call moves toward base case	n decreases: n → n-1 → n-2 → ... → 0
Return Value	Results combine back up the call stack	5! = 5 * 4! = 5 * 24 = 120

Recursion Patterns

Pattern	Description	Use Case
Linear Recursion	One recursive call per invocation	Factorial, sum of list
Binary Recursion	Two recursive calls per invocation	Fibonacci, binary tree traversal
Tail Recursion	Recursive call is last operation	Optimizable by compiler (not in Go)
Mutual Recursion	Functions call each other recursively	State machines, parsers
Memoization	Cache results to avoid recomputation	Dynamic programming problems

Recursion vs Iteration

Aspect	Recursion	Iteration
Code Clarity	Often simpler and more elegant	Can be more verbose
Memory Usage	Uses call stack (can overflow)	Constant memory for loops
Performance	Function call overhead	Generally faster
Problem Fit	Natural for tree/graph problems	Better for sequential processing
Tail Optimization	Not optimized in Go	N/A

Best Practices

Practice	Recommendation	Reason
Base Case	Always define clear base case(s)	Prevents infinite recursion and stack overflow
Progress	Ensure each call moves toward base case	Guarantees termination
Depth Limit	Consider maximum recursion depth	Go's stack size is limited
Memoization	Cache results for overlapping subproblems	Improves performance dramatically
Tail Recursion	Convert to iteration in Go	Go doesn't optimize tail calls
Testing	Test with small inputs first	Debug recursion logic before scaling

Previous: Closures Next: Pointers

How to Go