Go Recursion
Recursion happens when a function calls itself. Each call works on a smaller version of the same problem until it reaches a simple base case that stops the chain. Recursion is a powerful technique for problems that naturally break into repeated sub-problems.
The Two Rules of Recursion
Every recursive function needs:
1. Base Case ─── the condition that stops the recursion
2. Recursive Case ─── the call to itself with a smaller input
Without a base case, the function calls itself forever and crashes with a stack overflow.
Example – Factorial
Factorial of a number is the product of all integers from 1 to that number. Factorial of 5 = 5 × 4 × 3 × 2 × 1 = 120.
package main
import "fmt"
func factorial(n int) int {
if n == 0 { // base case
return 1
}
return n * factorial(n-1) // recursive case
}
func main() {
fmt.Println(factorial(5)) // 120
fmt.Println(factorial(3)) // 6
}
Call Stack Diagram for factorial(4)
factorial(4)
└── 4 * factorial(3)
└── 3 * factorial(2)
└── 2 * factorial(1)
└── 1 * factorial(0)
└── returns 1 ← base case
Unwinding:
factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
Example – Fibonacci Sequence
The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13… Each number is the sum of the two before it.
package main
import "fmt"
func fibonacci(n int) int {
if n <= 1 { // base case
return n
}
return fibonacci(n-1) + fibonacci(n-2) // recursive case
}
func main() {
for i := 0; i <= 7; i++ {
fmt.Printf("fibonacci(%d) = %d\n", i, fibonacci(i))
}
}
Output:
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8
fibonacci(7) = 13
Example – Countdown
package main
import "fmt"
func countdown(n int) {
if n == 0 { // base case
fmt.Println("Go!")
return
}
fmt.Println(n)
countdown(n - 1) // recursive case
}
func main() {
countdown(5)
}
Output:
5
4
3
2
1
Go!
Recursion vs Loop
| Feature | Recursion | Loop |
|---|---|---|
| Code style | Elegant for tree/nested problems | Straightforward for simple counts |
| Memory use | Uses call stack — higher memory | Lower memory |
| Risk | Stack overflow if base case is missing | Infinite loop if condition never false |
| Best for | Trees, graphs, divide-and-conquer | Counting, iterating over collections |
Key Points
- A recursive function must have a base case to stop calling itself
- Each recursive call should work on a smaller input toward the base case
- Recursion uses the call stack — deep recursion can cause a stack overflow
- Use recursion for problems like trees, nested structures, and divide-and-conquer algorithms
- Loops are more memory-efficient for simple repeated tasks