Recursion & Backtracking

Base case plus recursive case

A recursive function solves a problem by calling itself on a smaller version of the same problem. It needs exactly two ingredients:

• a base case — the smallest input, answered directly with no further calls,
• a recursive case — reduce the problem one step and combine the sub-answer.

Factorial is the textbook shape: 0! = 1 (base), and n! = n × (n-1)! (recursive). Each call peels off one n until it bottoms out, then the answers multiply back up as the stack unwinds.

graph TD
A["factorial(4)"] --> B["4 * factorial(3)"]
B --> C["3 * factorial(2)"]
C --> D["2 * factorial(1)"]
D --> E["1 * factorial(0)"]
E --> F["factorial(0) = 1  (base case)"]

The call stack and its limit

Each pending call keeps a stack frame — its parameters and locals — alive until it returns. A recursion n deep stacks n frames, so it costs O(n) space even when it returns a single number. Go grows a goroutine’s stack on demand, but not infinitely: run far enough (hundreds of thousands deep) and you hit fatal error: stack overflow. The fix is to bound the depth, switch to an iterative loop, or make the call a tail-free shape you can drive with an explicit stack.

package main

import "fmt"

// factorial is the canonical recursion: a base case and one smaller call.
func factorial(n int) int {
if n <= 1 { // base case: 0! and 1! are both 1
	return 1
}
return n * factorial(n-1) // recursive case: shrink n by one
}

// power computes base^exp recursively, halving exp each step so the
// depth is O(log exp) rather than O(exp).
func power(base, exp int) int {
if exp == 0 { // base case
	return 1
}
half := power(base, exp/2)
if exp%2 == 0 {
	return half * half
}
return base * half * half
}

func main() {
for n := 0; n <= 6; n++ {
	fmt.Printf("%d! = %d\n", n, factorial(n))
}
fmt.Printf("2^10 = %d\n", power(2, 10))
}

Backtracking: choose, explore, un-choose

Backtracking is recursion that builds a partial solution and undoes it. At each step you make a choice, recurse to explore everything that follows from it, then reverse the choice so the shared state is pristine for the next branch. It’s how you generate every permutation, subset, or board arrangement without duplicating work.

The undo step is the whole trick: because all branches share one slice or one used-set, you must leave it exactly as you found it.

graph TD
A["perm of [1,2,3]"] --> B["pick 1"]
A --> C["pick 2"]
A --> D["pick 3"]
B --> B1["1,2,3"]
B --> B2["1,3,2"]
C --> C1["2,1,3"]
C --> C2["2,3,1"]
D --> D1["3,1,2"]
D --> D2["3,2,1"]

package main

import (
"fmt"
"sort"
"strings"
)

// permute generates every ordering of nums using backtracking.
// current is the partial arrangement; used marks which indices are taken.
func permute(nums []int, used []bool, current []int, out *[][]int) {
if len(current) == len(nums) { // base case: a full permutation
	perm := make([]int, len(current))
	copy(perm, current)
	*out = append(*out, perm)
	return
}
for i := range nums {
	if used[i] {
		continue
	}
	// choose
	used[i] = true
	current = append(current, nums[i])
	// explore
	permute(nums, used, current, out)
	// un-choose: restore state for the next branch
	current = current[:len(current)-1]
	used[i] = false
}
}

func main() {
nums := []int{1, 2, 3}
var out [][]int
permute(nums, make([]bool, len(nums)), nil, &out)

// Sort the results so the printed output is deterministic.
lines := make([]string, 0, len(out))
for _, p := range out {
	lines = append(lines, fmt.Sprint(p))
}
sort.Strings(lines)
fmt.Printf("%d permutations:\n%s\n", len(out), strings.Join(lines, "\n"))
}

See also

• dynamic programming — memoize overlapping subproblems to kill the exponential blowup.
• binary trees — traversals are the purest recursion.
• graphs — DFS is recursion + a visited set; backtracking on a graph.
• stacks & queues — the explicit stack that replaces deep recursion.

Next: caching overlapping subproblems to turn exponential recursion into polynomial — dynamic programming.

Related topics