How to Write Recursive Functions in Go
You are building a tool to scan a directory for specific files. The directory structure is messy. Subfolders nest inside subfolders. You write a loop to check the current folder, but then you hit a subfolder. Do you write a new loop? What if there's a subfolder inside that one? Writing nested loops for unknown depth is a nightmare. Recursion handles this by letting the function call itself whenever it hits a new level. The code stays clean because the logic for a folder is the same regardless of how deep it sits.
Recursion is a function that calls itself. It breaks a problem into smaller versions of the same problem until the problem is small enough to solve directly. Think of it like a Russian nesting doll. You open the outer doll to find a smaller one inside. You keep opening dolls until you reach the tiniest one that has nothing inside. That tiny doll is the base case. Once you hit it, you start closing the dolls back up, carrying the result outward. In code, the base case stops the function from calling itself forever. Without a base case, the function calls itself until the program runs out of memory and crashes.
Minimal example
Here's the simplest recursive pattern: a function that calls itself with a smaller argument until it hits a stopping condition.
package main
import "fmt"
// Factorial computes n! using recursion.
func Factorial(n int) int {
// Base case returns 1 for n <= 1 to stop recursion.
if n <= 1 {
return 1
}
// Recursive call reduces n by 1 and multiplies the result.
return n * Factorial(n-1)
}
func main() {
// Prints 120 for 5!.
fmt.Println(Factorial(5))
}
Public names start with a capital letter. Factorial is exported. Private start lowercase. No keywords like public or private. The capital letter controls visibility across packages.
How the stack works
When Factorial(3) runs, the program creates a stack frame for the call. Inside that frame, n is 3. The function checks the base case, fails, and calls Factorial(2). A new stack frame appears on top of the first one. This repeats until Factorial(1) hits the base case and returns 1. The stack frames unwind one by one, multiplying the results as they go. Each frame holds its own copy of n. The stack grows with every call and shrinks as calls return.
Go goroutines have a small initial stack that grows dynamically. This helps recursion compared to languages with fixed stack sizes, but the limit still exists. The default stack size is small, often 2KB to 4KB initially, growing as needed. However, the total memory per goroutine is limited. Deep recursion consumes this memory quickly. The stack is a LIFO structure. Every function call pushes a frame. Every return pops a frame. The frame contains local variables, arguments, and the return address.
Realistic example: tree traversal
Recursion shines when the data structure is recursive. A tree node contains references to other nodes, which contain references to more nodes. A recursive function mirrors this shape naturally. Trees appear everywhere. File systems are trees. JSON documents are trees. DOM elements are trees. When you parse a nested JSON config, you often write a recursive function to walk the map. The function checks the type of the value. If it's a map, it calls itself for each child. If it's a string, it processes the string. This pattern repeats until the structure is fully traversed.
Here's a function that sums all values in a binary tree. The structure defines the node, and the function walks the branches.
package main
// TreeNode represents a node in a binary tree.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// SumTree adds all values in the binary tree recursively.
func SumTree(node *TreeNode) int {
// Nil check handles leaf boundaries and empty trees.
if node == nil {
return 0
}
// Accumulate current value and recurse into children.
return node.Val + SumTree(node.Left) + SumTree(node.Right)
}
If you attach the sum function to the struct as a method, the receiver name should be short. Use (n *TreeNode) Sum() int, not (this *TreeNode). One or two letters matching the type is the convention. This keeps method signatures readable and aligns with standard library style.
Pitfalls and runtime errors
Go does not perform tail-call optimization. The compiler does not transform recursive calls into loops automatically. If you recurse too deeply, the program exhausts the stack space and panics. The runtime stops execution with a stack overflow error. This usually happens when processing very deep structures without a base case, or when the base case is unreachable.
The runtime panics with fatal error: stack overflow if the call depth gets too high. This isn't a compiler error; the code compiles fine. The crash happens at runtime when the stack fills up. Another common mistake is forgetting the nil check in a tree traversal. If you access a field on a nil pointer, the runtime panics with panic: runtime error: invalid memory address or nil pointer dereference. Always verify the base case is reachable and the recursive step moves closer to it.
Recursion is elegant until the stack runs out. Check your base case before you run the code.
Returning multiple values
Go functions can return multiple values. Recursion works naturally with this feature. You might need to return a computed value and a flag, or a result and an error. The base case must provide values for every return slot. The recursive step merges the results from the sub-calls. This pattern is common in parsers or validators where you return the parsed data and an error status.
Here's a function that returns both the maximum value and the depth of the tree.
// FindMaxAndDepth returns the maximum value and the depth of the tree.
func FindMaxAndDepth(node *TreeNode) (int, int) {
if node == nil {
// Base case returns zero value for max and negative depth for empty.
return 0, -1
}
// Recurse left and right to get sub-results.
leftMax, leftDepth := FindMaxAndDepth(node.Left)
rightMax, rightDepth := FindMaxAndDepth(node.Right)
// Determine current max and depth based on children.
currentMax := node.Val
if leftMax > currentMax {
currentMax = leftMax
}
if rightMax > currentMax {
currentMax = rightMax
}
// Depth is one plus the maximum child depth.
depth := 1 + leftDepth
if rightDepth > depth {
depth = rightDepth
}
return currentMax, depth
}
Cancellation with context
Long-running recursive operations need a way to stop. If you are walking a massive directory tree, the user might want to cancel the scan. Pass a context.Context as the first argument. Check the context at every step. If the context is cancelled, return immediately. This prevents the function from continuing work after the caller has lost interest. The context flows down the recursion chain, allowing any level to abort the entire operation.
context.Context always goes as the first parameter, conventionally named ctx. Functions that take a context should respect cancellation and deadlines. This convention is universal in Go. It enables clean shutdown and timeout handling across the call graph.
Iterative alternative
When depth is unpredictable or large, replace recursion with an explicit stack. You manage the stack yourself using a slice, which allocates memory on the heap instead of the call stack. This prevents stack overflow panics. Using a slice as a stack is efficient. append adds to the end. Slicing stack[:len(stack)-1] removes from the end. This gives O(1) push and pop operations. The slice allocates on the heap, so memory usage is flexible. You can process millions of nodes without crashing, limited only by available RAM. This trade-off gives you safety at the cost of slightly more code. The iterative version is often longer but robust.
Here's the tree sum rewritten with an explicit stack.
// SumTreeIterative sums the tree using a heap-allocated stack.
func SumTreeIterative(root *TreeNode) int {
if root == nil {
return 0
}
// Initialize stack with the root node.
stack := []*TreeNode{root}
sum := 0
for len(stack) > 0 {
// Pop node from the top of the stack.
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
sum += node.Val
// Push right child first so left is processed first.
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left != nil {
stack = append(stack, node.Left)
}
}
return sum
}
gofmt is mandatory. Don't argue about indentation; let the tool decide. Most editors run it on save. The community expects consistent formatting. Trust the tool.
When to use recursion
Use recursion when the data structure is naturally recursive and depth is bounded. Use recursion when code readability matters more than raw performance for small inputs. Use an explicit stack when the input depth is unbounded or could exceed the stack limit. Use iteration with a loop when you need to process a flat sequence without branching. Use a worker pool when you need to parallelize the traversal across multiple cores.
Pick the tool that matches the shape of the data. Recursion for trees, loops for lists, stacks for deep unknowns.