Skip to main content
Go supports recursive functions, which are functions that call themselves. Recursion is a powerful technique for solving problems that can be broken down into smaller, similar subproblems.

​
Basic Recursion

Here’s a classic example of recursion - calculating factorial: 
func fact(n int) int {
    if n == 0 {
        return 1
    }
    return n * fact(n-1)
}
This function calls itself until it reaches the base case of fact(0).
Every recursive function needs a base case (a condition that stops the recursion) to avoid infinite loops and stack overflow errors.

​
How Recursion Works

When you call fact(7), the execution flow looks like this: 
fact(7) = 7 * fact(6)
        = 7 * (6 * fact(5))
        = 7 * (6 * (5 * fact(4)))
        = 7 * (6 * (5 * (4 * fact(3))))
        = 7 * (6 * (5 * (4 * (3 * fact(2)))))
        = 7 * (6 * (5 * (4 * (3 * (2 * fact(1))))))
        = 7 * (6 * (5 * (4 * (3 * (2 * (1 * fact(0)))))))
        = 7 * (6 * (5 * (4 * (3 * (2 * (1 * 1))))))
        = 5040

​
Recursive Anonymous Functions

Anonymous functions can also be recursive, but this requires explicitly declaring a variable to store the function: 
var fib func(n int) int

fib = func(n int) int {
    if n < 2 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

fmt.Println(fib(7))  // Output: 13
The variable fib must be declared with var before the function is defined. This allows Go to know which function to call when fib is referenced inside the anonymous function.

​
Complete Example

package main

import "fmt"

// Named recursive function for factorial
func fact(n int) int {
    if n == 0 {
        return 1
    }
    return n * fact(n-1)
}

func main() {
    fmt.Println(fact(7))  // Output: 5040

    // Anonymous recursive function for Fibonacci
    var fib func(n int) int
    
    fib = func(n int) int {
        if n < 2 {
            return n
        }
        return fib(n-1) + fib(n-2)
    }
    
    fmt.Println(fib(7))  // Output: 13
}

​
Common Recursive Patterns

Tree Traversal

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

func sumTree(node *Node) int {
    if node == nil {
        return 0
    }
    return node.Value + 
           sumTree(node.Left) + 
           sumTree(node.Right)
}

List Processing

func sumSlice(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    return nums[0] + sumSlice(nums[1:])
}

result := sumSlice([]int{1, 2, 3, 4, 5})
// result = 15

​
Tail Recursion Optimization

Go doesn’t guarantee tail call optimization, so deeply recursive functions can cause stack overflow. Consider using iteration or helper functions with accumulators: 
// Not tail-recursive (can overflow)
func factorial(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorial(n-1)
}

// Tail-recursive with accumulator (still not optimized by Go)
func factorialHelper(n, acc int) int {
    if n == 0 {
        return acc
    }
    return factorialHelper(n-1, n*acc)
}

func factorialTail(n int) int {
    return factorialHelper(n, 1)
}

// Iterative alternative (recommended for deep recursion)
func factorialIter(n int) int {
    result := 1
    for i := 2; i <= n; i++ {
        result *= i
    }
    return result
}
Go does not perform tail call optimization. For deeply recursive functions (thousands of calls), prefer iterative solutions to avoid stack overflow.

​
Memoization for Recursive Functions

Some recursive functions (like Fibonacci) recalculate the same values repeatedly. Memoization can dramatically improve performance: 
func fibonacci() func(int) int {
    cache := make(map[int]int)
    var fib func(int) int
    
    fib = func(n int) int {
        if n < 2 {
            return n
        }
        
        if val, found := cache[n]; found {
            return val
        }
        
        result := fib(n-1) + fib(n-2)
        cache[n] = result
        return result
    }
    
    return fib
}

func main() {
    fib := fibonacci()
    fmt.Println(fib(40))  // Much faster with memoization
}

​
Mutual Recursion

Multiple functions can call each other recursively: 
func isEven(n int) bool {
    if n == 0 {
        return true
    }
    return isOdd(n - 1)
}

func isOdd(n int) bool {
    if n == 0 {
        return false
    }
    return isEven(n - 1)
}

​
Best Practices

Every recursive function must have a condition that stops the recursion:
func countdown(n int) {
    if n <= 0 {  // Base case
        fmt.Println("Done!")
        return
    }
    fmt.Println(n)
    countdown(n - 1)
}
Go’s default stack size is limited. For potentially deep recursion, validate input or use iteration:
func safeFact(n int) (int, error) {
    if n > 20 {  // Prevent overflow and deep recursion
        return 0, errors.New("input too large")
    }
    if n == 0 {
        return 1, nil
    }
    prev, err := safeFact(n - 1)
    if err != nil {
        return 0, err
    }
    return n * prev, nil
}
Recursion is ideal for naturally recursive problems (trees, graphs, divide-and-conquer), but iteration may be clearer for simple loops.
Recursive functions have overhead from function calls. For performance-critical code or deep recursion, consider iterative alternatives.

​
When to Use Recursion

  • Tree and graph traversal
  • Divide-and-conquer algorithms (quicksort, mergesort)
  • Problems with recursive structure (Fibonacci, factorial)
  • Backtracking algorithms
  • Parsing nested structures

​
When to Avoid Recursion

  • Simple iteration would be clearer
  • Very deep recursion (risk of stack overflow)
  • Performance-critical tight loops
  • When Go’s lack of tail call optimization is problematic

​
Key Takeaways

  • Recursive functions call themselves to solve subproblems
  • Every recursive function needs a base case to terminate
  • Anonymous functions can be recursive with proper variable declaration
  • Go doesn’t optimize tail recursion - consider iteration for deep recursion
  • Memoization can dramatically improve recursive function performance
  • Use recursion when it makes the problem clearer, not just because you can

Build docs developers (and LLMs) love

Get started for freeTalk to us