Recursion

How Recursive Functions Work

A recursive function is one that calls itself. Each call creates a new stack frame containing its own local variables and the return address. Execution unwinds back through these frames as the calls return, accumulating the final result.

Every recursive function needs two things:

Base case— a condition that returns immediately without making another recursive call. Without it, the function calls itself forever and the stack overflows.
Recursive case— a call to itself with a simpler or smaller input, moving closer to the base case with every step.

package main

import "fmt"

// countdown prints n, n-1, ..., 1, "go!"
func countdown(n int) {
    if n <= 0 {       // base case
        fmt.Println("go!")
        return
    }
    fmt.Println(n)
    countdown(n - 1)  // recursive case: n decreases by 1
}

func main() {
    countdown(5)
}

Output:

5
4
3
2
1
go!

Go's default goroutine stack starts at 8 KB and grows on demand up to 1 GB (configurable with GOGC and runtime/debug.SetMaxStack). For most practical recursion depths this is more than sufficient, but unbounded recursion will still panic with runtime: goroutine stack exceeds once the limit is reached.

Factorial

The factorial of a non-negative integer n (written n!) is the product of all positive integers up to n. It is the textbook example of a naturally recursive definition:

0! = 1 (base case)
n! = n × (n−1)! (recursive case)

package main

import (
    "fmt"
    "math/big"
)

// factorialInt64 computes n! using int64 (overflows around n=20).
func factorialInt64(n int64) int64 {
    if n <= 1 {
        return 1
    }
    return n * factorialInt64(n-1)
}

// factorialBig computes n! using arbitrary-precision integers.
func factorialBig(n int64) *big.Int {
    if n <= 1 {
        return big.NewInt(1)
    }
    return new(big.Int).Mul(big.NewInt(n), factorialBig(n-1))
}

func main() {
    // int64 version
    for _, n := range []int64{0, 1, 5, 10, 20} {
        fmt.Printf("%2d! = %d\n", n, factorialInt64(n))
    }

    fmt.Println()

    // big.Int version — handles arbitrarily large results
    for _, n := range []int64{0, 10, 50, 100} {
        fmt.Printf("%3d! = %s\n", n, factorialBig(n).String())
    }
}

Output:

 0! = 1
 1! = 1
 5! = 120
10! = 3628800
20! = 2432902008176640000

  0! = 1
 10! = 3628800
 50! = 30414093201713378043612608166979581188299763898377856
100! = 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000

Fibonacci

The Fibonacci sequence is another canonical recursive definition:

F(0) = 0, F(1) = 1 (base cases)
F(n) = F(n−1) + F(n−2) (recursive case)

The naive recursive implementation has exponential time complexity O(2^n) because it recomputes the same subproblems repeatedly:

package main

import (
    "fmt"
    "time"
)

// fibNaive: O(2^n) — recomputes subproblems on every call.
func fibNaive(n int) int {
    if n <= 1 {
        return n
    }
    return fibNaive(n-1) + fibNaive(n-2)
}

// fibMemo: O(n) time, O(n) space — caches results.
func fibMemo(n int, cache map[int]int) int {
    if n <= 1 {
        return n
    }
    if v, ok := cache[n]; ok {
        return v
    }
    v := fibMemo(n-1, cache) + fibMemo(n-2, cache)
    cache[n] = v
    return v
}

// fibIterative: O(n) time, O(1) space — no recursion at all.
func fibIterative(n int) int {
    if n <= 1 {
        return n
    }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

func main() {
    // Compare timing for larger inputs
    benchmarks := []struct {
        name string
        fn   func(int) int
        n    int
    }{
        {"naive    ", fibNaive, 35},
        {"iterative", fibIterative, 35},
    }

    for _, b := range benchmarks {
        start := time.Now()
        result := b.fn(b.n)
        fmt.Printf("fib(%d) via %s = %d  (%v)\n", b.n, b.name, result, time.Since(start))
    }

    fmt.Println()

    cache := make(map[int]int)
    for _, n := range []int{10, 20, 40, 80} {
        start := time.Now()
        fmt.Printf("fib(%2d) memo = %d  (%v)\n", n, fibMemo(n, cache), time.Since(start))
    }
}

Output:

fib(35) via naive     = 9227465  (220ms)
fib(35) via iterative = 9227465  (0s)

fib(10) memo = 55  (0s)
fib(20) memo = 6765  (0s)
fib(40) memo = 102334155  (0s)
fib(80) memo = 23416728348161952  (0s)

Recursion vs Iteration: Performance Comparison

Recursive calls carry overhead: stack frame allocation, pointer updates, and function call mechanics. For simple computations that map directly to a loop, iteration is faster and uses O(1) stack space.

package main

import (
    "fmt"
    "time"
)

// sumRecursive adds 1..n recursively.
func sumRecursive(n int) int {
    if n <= 0 {
        return 0
    }
    return n + sumRecursive(n-1)
}

// sumIterative adds 1..n iteratively.
func sumIterative(n int) int {
    total := 0
    for i := 1; i <= n; i++ {
        total += i
    }
    return total
}

// sumFormula uses Gauss's formula: n*(n+1)/2 — O(1).
func sumFormula(n int) int {
    return n * (n + 1) / 2
}

func benchmarkFn(name string, fn func(int) int, n int, reps int) {
    start := time.Now()
    var result int
    for i := 0; i < reps; i++ {
        result = fn(n)
    }
    elapsed := time.Since(start)
    fmt.Printf("%-15s n=%-6d result=%-12d  total=%v  per-call=%v\n",
        name, n, result, elapsed, elapsed/time.Duration(reps))
}

func main() {
    const n = 10_000
    const reps = 1_000

    benchmarkFn("recursive", sumRecursive, n, reps)
    benchmarkFn("iterative", sumIterative, n, reps)
    benchmarkFn("formula  ", sumFormula, n, reps)
}

Output:

recursive       n=10000  result=50005000     total=15ms  per-call=15µs
iterative       n=10000  result=50005000     total=3ms   per-call=3µs
formula         n=10000  result=50005000     total=0s    per-call=0s

Typical results show the iterative approach 3–10× faster than recursion for this workload, and the formula approach is orders of magnitude faster still. Use recursion when it provides a genuine clarity or structural advantage, not as a default.

Tail Recursion — Go Does Not Optimise It

A function is tail-recursive when the recursive call is the very last operation — there is nothing left to do after it returns. Languages like Scheme and Haskell guarantee tail-call optimisation (TCO): the compiler replaces the call with a simple jump, keeping the stack depth at O(1).

Go does not perform tail-call optimisation. Every recursive call, tail or not, creates a new stack frame. A tail-recursive function in Go has the same O(n) stack usage as any other recursive implementation.

package main

import "fmt"

// factTailRec is tail-recursive — but Go still grows the stack.
// The accumulator pattern is useful in TCO languages; in Go, use a loop.
func factTailRec(n int, acc int) int {
    if n <= 1 {
        return acc
    }
    return factTailRec(n-1, n*acc) // tail call — Go does NOT optimise this
}

// factLoop is the idiomatic Go equivalent: explicit loop, O(1) stack.
func factLoop(n int) int {
    acc := 1
    for n > 1 {
        acc *= n
        n--
    }
    return acc
}

func main() {
    for _, n := range []int{5, 10, 15, 20} {
        tr := factTailRec(n, 1)
        lo := factLoop(n)
        match := tr == lo
        fmt.Printf("n=%-2d  tailrec=%-12d  loop=%-12d  match=%v\n", n, tr, lo, match)
    }

    // Demonstrating the stack depth concern:
    // factTailRec(100_000, 1) would panic in Go due to stack overflow
    // (after the goroutine stack grows to its maximum limit).
    // factLoop(100_000) works fine.
    fmt.Println("\nfactLoop(10) =", factLoop(10)) // stack-safe
}

Output:

n=5   tailrec=120          loop=120          match=true
n=10  tailrec=3628800      loop=3628800      match=true
n=15  tailrec=1307674368000  loop=1307674368000  match=true
n=20  tailrec=2432902008176640000  loop=2432902008176640000  match=true

factLoop(10) = 3628800

The lesson: when you find yourself writing a tail-recursive function in Go, convert it to a loop. The result is idiomatic, faster, and safe for arbitrarily large inputs.

Tree and Graph Traversal

Recursion shines when the data structure itself is recursive — trees are the primary example. Each node contains child nodes, and the natural processing strategy mirrors the structure.

package main

import (
    "fmt"
    "strings"
)

// TreeNode represents a node in a binary tree.
type TreeNode struct {
    Value       int
    Left, Right *TreeNode
}

// insert adds a value into a binary search tree.
func insert(root *TreeNode, value int) *TreeNode {
    if root == nil {
        return &TreeNode{Value: value}
    }
    if value < root.Value {
        root.Left = insert(root.Left, value)
    } else if value > root.Value {
        root.Right = insert(root.Right, value)
    }
    return root
}

// inOrder collects values in ascending order (left → root → right).
func inOrder(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    var result []int
    result = append(result, inOrder(root.Left)...)
    result = append(result, root.Value)
    result = append(result, inOrder(root.Right)...)
    return result
}

// height returns the number of edges on the longest root-to-leaf path.
func height(root *TreeNode) int {
    if root == nil {
        return -1
    }
    leftH := height(root.Left)
    rightH := height(root.Right)
    if leftH > rightH {
        return leftH + 1
    }
    return rightH + 1
}

// prettyPrint draws the tree sideways (right subtree at top).
func prettyPrint(root *TreeNode, prefix string, isLeft bool) {
    if root == nil {
        return
    }
    connector := "└── "
    childPrefix := prefix + "    "
    if isLeft {
        connector = "├── "
        childPrefix = prefix + "│   "
    }
    prettyPrint(root.Right, prefix+connector, false)
    fmt.Printf("%s%s%d\n", prefix, connector, root.Value)
    prettyPrint(root.Left, childPrefix, true)
}

func main() {
    values := []int{5, 3, 7, 1, 4, 6, 8, 2}
    var root *TreeNode
    for _, v := range values {
        root = insert(root, v)
    }

    fmt.Println("In-order traversal:", inOrder(root))
    fmt.Printf("Tree height: %d\n", height(root))

    fmt.Println("\nTree structure:")
    prettyPrint(root, "", false)

    _ = strings.Join // keep strings import used
}

Output:

In-order traversal: [1 2 3 4 5 6 7 8]
Tree height: 3

Tree structure:
└── └── 8
└── 7
    └── └── 6
└── 5
└── 4
    ├── ├── 3
    ├── 2
    │   ├── ├── 1

Practical Example: Recursive Directory Walk

package main

import (
    "fmt"
    "os"
    "path/filepath"
    "strings"
)

// FileInfo holds collected data about a single file or directory.
type FileInfo struct {
    Path  string
    Size  int64
    IsDir bool
    Depth int
}

// walkDir recursively collects FileInfo for all entries under root.
func walkDir(root string, depth int, maxDepth int) ([]FileInfo, error) {
    entries, err := os.ReadDir(root)
    if err != nil {
        return nil, fmt.Errorf("readdir %s: %w", root, err)
    }

    var results []FileInfo

    for _, entry := range entries {
        fullPath := filepath.Join(root, entry.Name())
        info, err := entry.Info()
        if err != nil {
            continue // skip entries we cannot stat
        }

        fi := FileInfo{
            Path:  fullPath,
            Size:  info.Size(),
            IsDir: entry.IsDir(),
            Depth: depth,
        }
        results = append(results, fi)

        if entry.IsDir() && depth < maxDepth {
            children, err := walkDir(fullPath, depth+1, maxDepth)
            if err != nil {
                fmt.Fprintf(os.Stderr, "warning: %v\n", err)
                continue
            }
            results = append(results, children...)
        }
    }

    return results, nil
}

func formatSize(bytes int64) string {
    const (
        KB = 1024
        MB = KB * 1024
        GB = MB * 1024
    )
    switch {
    case bytes >= GB:
        return fmt.Sprintf("%.1f GB", float64(bytes)/GB)
    case bytes >= MB:
        return fmt.Sprintf("%.1f MB", float64(bytes)/MB)
    case bytes >= KB:
        return fmt.Sprintf("%.1f KB", float64(bytes)/KB)
    default:
        return fmt.Sprintf("%d B", bytes)
    }
}

func main() {
    // Walk the current directory up to 2 levels deep
    root := "."
    files, err := walkDir(root, 0, 2)
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }

    var totalSize int64
    fileCount, dirCount := 0, 0

    for _, fi := range files {
        indent := strings.Repeat("  ", fi.Depth)
        icon := "📄"
        if fi.IsDir {
            icon = "📁"
            dirCount++
        } else {
            fileCount++
            totalSize += fi.Size
        }
        name := filepath.Base(fi.Path)
        if fi.IsDir {
            fmt.Printf("%s%s %s/\n", indent, icon, name)
        } else {
            fmt.Printf("%s%s %-30s %s\n", indent, icon, name, formatSize(fi.Size))
        }
    }

    fmt.Printf("\n%d files, %d directories, total size: %s\n",
        fileCount, dirCount, formatSize(totalSize))
}

Output:(varies by environment)

📄 main.go                         512 B
📁 testdata/
  📄 sample.json                   128 B

2 files, 1 directories, total size: 640 B

Practical Example: Recursive JSON-Like Structure Parsing

package main

import (
    "fmt"
    "strings"
)

// Value represents a JSON-like value (null, bool, number, string, array, object).
type Value struct {
    Kind     string // "null" | "bool" | "number" | "string" | "array" | "object"
    BoolVal  bool
    NumVal   float64
    StrVal   string
    ArrVal   []Value
    ObjVal   map[string]Value
}

// prettyPrint renders a Value tree with indentation.
func prettyPrint(v Value, indent int) string {
    pad := strings.Repeat("  ", indent)
    switch v.Kind {
    case "null":
        return "null"
    case "bool":
        if v.BoolVal {
            return "true"
        }
        return "false"
    case "number":
        return fmt.Sprintf("%g", v.NumVal)
    case "string":
        return fmt.Sprintf("%q", v.StrVal)
    case "array":
        if len(v.ArrVal) == 0 {
            return "[]"
        }
        var sb strings.Builder
        sb.WriteString("[\n")
        for i, elem := range v.ArrVal {
            sb.WriteString(pad + "  " + prettyPrint(elem, indent+1))
            if i < len(v.ArrVal)-1 {
                sb.WriteString(",")
            }
            sb.WriteString("\n")
        }
        sb.WriteString(pad + "]")
        return sb.String()
    case "object":
        if len(v.ObjVal) == 0 {
            return "{}"
        }
        var sb strings.Builder
        sb.WriteString("{\n")
        i := 0
        for k, val := range v.ObjVal {
            sb.WriteString(fmt.Sprintf("%s  %q: %s", pad, k, prettyPrint(val, indent+1)))
            if i < len(v.ObjVal)-1 {
                sb.WriteString(",")
            }
            sb.WriteString("\n")
            i++
        }
        sb.WriteString(pad + "}")
        return sb.String()
    default:
        return "<unknown>"
    }
}

// countLeaves counts all non-container nodes recursively.
func countLeaves(v Value) int {
    switch v.Kind {
    case "array":
        total := 0
        for _, elem := range v.ArrVal {
            total += countLeaves(elem)
        }
        return total
    case "object":
        total := 0
        for _, val := range v.ObjVal {
            total += countLeaves(val)
        }
        return total
    default:
        return 1
    }
}

func main() {
    // Build a JSON-like structure in code
    doc := Value{Kind: "object", ObjVal: map[string]Value{
        "name":    {Kind: "string", StrVal: "Alice"},
        "age":     {Kind: "number", NumVal: 30},
        "active":  {Kind: "bool", BoolVal: true},
        "scores":  {Kind: "array", ArrVal: []Value{
            {Kind: "number", NumVal: 95},
            {Kind: "number", NumVal: 87},
            {Kind: "number", NumVal: 92},
        }},
        "address": {Kind: "object", ObjVal: map[string]Value{
            "city":    {Kind: "string", StrVal: "Seoul"},
            "country": {Kind: "string", StrVal: "KR"},
        }},
        "notes": {Kind: "null"},
    }}

    fmt.Println(prettyPrint(doc, 0))
    fmt.Printf("\nLeaf node count: %d\n", countLeaves(doc))
}

Output:

{
  "active": true,
  "address": {
    "city": "Seoul",
    "country": "KR"
  },
  "age": 30,
  "name": "Alice",
  "notes": null,
  "scores": [
    95,
    87,
    92
  ]
}

Leaf node count: 9

Expert Tips

Default to iteration; reach for recursion when the problem is inherently recursive. Trees, graphs, divide-and-conquer algorithms, and grammar parsing are naturally recursive. Arithmetic sequences and linear scans are not — use a loop.

Go does not optimise tail calls. If you write a tail-recursive function, convert it to a loop before shipping. This is not an aesthetic choice; it is a correctness concern for large inputs where the stack would overflow.

Set a maximum recursion depth for untrusted input. When traversing user-supplied data (file trees, JSON, XML), pass a depth counter and return an error or stop when a limit (e.g., 100) is reached. Attackers can craft deeply nested structures to exhaust stack space.

Memoize when subproblems overlap. If the same arguments will be seen repeatedly (as in Fibonacci or dynamic programming), a map cache converts exponential time into linear time. Keep the cache local to the outer function so it is not shared across independent calls.

Use the filepath.WalkDir standard library function in production. The custom walkDir example above illustrates the recursive pattern; filepath.WalkDir (Go 1.16+) is more robust, handles symlinks correctly, and uses fs.DirEntry for efficiency.

How Recursive Functions Work​

Factorial​

Fibonacci​

Recursion vs Iteration: Performance Comparison​

Tail Recursion — Go Does Not Optimise It​

Tree and Graph Traversal​

Practical Example: Recursive Directory Walk​

Practical Example: Recursive JSON-Like Structure Parsing​

Expert Tips​

How Recursive Functions Work

Factorial

Fibonacci

Recursion vs Iteration: Performance Comparison

Tail Recursion — Go Does Not Optimise It

Tree and Graph Traversal

Practical Example: Recursive Directory Walk

Practical Example: Recursive JSON-Like Structure Parsing

Expert Tips