Chapter 45: Recursion
1. What is Recursion? (The Simplest Definition)
Recursion means:
A function that calls itself (directly or indirectly) to solve a smaller version of the same problem.
The key sentence every beginner needs to remember:
“To solve a big problem, I solve a smaller version of the same problem… and trust that the smaller one will eventually solve itself.”
But recursion only works if you have two things:
- Base case (the smallest problem that I can solve without calling myself again)
- Recursive case (the step where I make the problem smaller and call myself again)
Without a proper base case, recursion never stops → infinite recursion → stack overflow crash.
2. Classic First Example – Factorial (most common teaching example)
Factorial definition (mathematical):
|
0 1 2 3 4 5 6 7 |
5! = 5 × 4 × 3 × 2 × 1 = 120 0! = 1 (by definition) |
Recursive definition (the way recursion thinks):
|
0 1 2 3 4 5 6 7 |
n! = n × (n-1)! when n > 0 n! = 1 when n = 0 ← base case |
Now the Go code:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
package main import "fmt" func factorial(n int) int { // Base case – the smallest problem if n == 0 || n == 1 { return 1 } // Recursive case – make problem smaller return n * factorial(n-1) } func main() { fmt.Println("5! =", factorial(5)) // 120 fmt.Println("0! =", factorial(0)) // 1 fmt.Println("1! =", factorial(1)) // 1 fmt.Println("6! =", factorial(6)) // 720 } |
3. Step-by-Step Execution (Very Important – Trace It!)
Let’s trace factorial(5) mentally:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
factorial(5) = 5 * factorial(4) = 5 * (4 * factorial(3)) = 5 * (4 * (3 * factorial(2))) = 5 * (4 * (3 * (2 * factorial(1)))) = 5 * (4 * (3 * (2 * 1))) ← base case reached = 5 * (4 * (3 * 2)) = 5 * (4 * 6) = 5 * 24 = 120 |
Call stack visualization (what happens in memory):
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
factorial(5) waiting for factorial(4) factorial(4) waiting for factorial(3) factorial(3) waiting for factorial(2) factorial(2) waiting for factorial(1) factorial(1) → returns 1 (base case) ← returns 2*1 = 2 ← returns 3*2 = 6 ← returns 4*6 = 24 ← returns 5*24 = 120 |
Every recursive call adds a new layer to the call stack. When base case is reached → stack starts unwinding and multiplies back.
4. Another Classic Example – Fibonacci (very common interview question)
Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
Rule:
|
0 1 2 3 4 5 6 7 8 |
fib(0) = 0 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2) for n > 1 |
Naive recursive version:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
func fib(n int) int { if n == 0 { return 0 } if n == 1 { return 1 } return fib(n-1) + fib(n-2) } func main() { for i := 0; i <= 10; i++ { fmt.Printf("fib(%d) = %d\n", i, fib(i)) } } |
Warning: this version is very slow for large n (exponential time O(2ⁿ)) — we usually use dynamic programming / memoization / iterative version in real code.
5. Real-World & Useful Recursive Patterns in Go
Pattern 1: Tree / directory traversal
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
func printFiles(path string, indent string) { files, err := os.ReadDir(path) if err != nil { return } for _, file := range files { fmt.Println(indent + file.Name()) if file.IsDir() { printFiles(path+"/"+file.Name(), indent+" ") // recursive call } } } |
Pattern 2: JSON / nested data processing
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
type Node struct { Value int Children []Node } func sumTree(node Node) int { total := node.Value for _, child := range node.Children { total += sumTree(child) // recurse on each child } return total } |
6. When NOT to Use Recursion in Go (Very Important)
- Large input size → stack overflow (Go default stack is 1–8 MB depending on version/platform)
- Deep recursion (thousands of levels) → use iterative solution (loop + stack/queue)
- Performance-critical code → recursion usually slower + more memory than iteration
Rule of thumb 2025–2026:
Use recursion when:
- Problem is naturally recursive (tree, graph, divide-and-conquer)
- Depth is small (< 1000–2000 calls)
- Code clarity is more important than micro-optimization
Use iteration (for / while) when:
- Input can be large
- You want predictable memory usage
- Performance is critical
7. Quick Practice – Try Writing These
- Recursive function power(base, exp int) int → base^exp (base case: exp == 0 → return 1)
- Recursive function reverse(s string) string → “hello” → “olleh”
- Recursive function countDown(n int) that prints n → 1 → “Blast off!”
Which one felt most natural?
Any part still confusing?
- How to trace recursive calls step-by-step?
- Base case vs recursive case – which one is more important?
- Why recursion sometimes slower than loops?
- Or ready to see memoization / tail recursion next?
Keep writing small recursive functions — once you really feel how the call stack builds and unwinds, recursion becomes one of the most satisfying tools in programming.
You’re doing really great — keep asking! 💪🇮🇳🚀
