Skip to content

Go Recursion

Recursion is a technique where a function calls itself to solve a problem. It's useful for tasks that can be broken down into smaller, similar sub-tasks.

Basic Example: Factorial

A common example is calculating a factorial (n!).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
package main

import "fmt"

func fact(n int) int {
    // Base case: without this, the function would call itself forever
    if n == 0 {
        return 1
    }
    // Recursive call: the function calls itself with a smaller value
    return n * fact(n-1)
}

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

Essential Rules for Recursion

  1. Base Case: You must have a condition that stops the recursion (e.g., if n == 0).
  2. Progress: Each recursive call must move closer to the base case.

When to use Recursion?

Recursion are used in:

  1. Mathematical sequences (like Factorial or Fibonacci).
  2. Navigating tree-like structures (like file directories or JSON objects). Particularly in graph structures, we use recursion to reach nodes.

Important Note on Performance

Go does not optimize recursive calls (no tail-call optimization). For very deep recursion, a standard loop (for loop) is usually more efficient and avoids "stack overflow" errors.