GGistDev

Recursion in Go

Recursion is a function calling itself to solve subproblems. Ensure a base case and progress toward it.

Basics

A recursive function must have a base case that stops the recursion and a step that moves toward it.

func fact(n int) int {
    if n <= 1 { return 1 }        // base case
    return n * fact(n-1)          // progress
}

Fibonacci (memoized)

The naive recursive Fibonacci is exponential; memoization turns it into linear time by caching results.

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

// Better with memoization
func fibMemo() func(int) int {
    cache := map[int]int{}
    var f func(int) int
    f = func(n int) int {
        if n < 2 { return n }
        if v, ok := cache[n]; ok { return v }
        v := f(n-1) + f(n-2)
        cache[n] = v
        return v
    }
    return f
}

Tree traversal

Trees and graphs are natural fits for recursion. Always guard against nil pointers.

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

func Sum(root *Node) int {
    if root == nil { return 0 }
    return root.Val + Sum(root.Left) + Sum(root.Right)
}

Tail recursion

  • Go does not guarantee tail-call optimization; prefer loops for deep recursions
func factIter(n int) int {
    res := 1
    for n > 1 { res *= n; n-- }
    return res
}

When to use

  • Natural divide-and-conquer (trees, DFS, permutations)
  • When iterative code is significantly less clear

Cautions

  • Stack limits: avoid extremely deep recursion
  • Memoize or convert to iterative algorithms for performance when needed
  • Beware shared state across recursive calls; pass parameters explicitly

Summary

  • Always define a base case and ensure progress
  • Prefer iterative or memoized approaches for performance and depth safety
←PreviousClosures
NextRange→