Understanding Stack Overflow in Go
Stack overflow errors appear as:
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow
runtime stack:
runtime.throw(0x10b7c0, 0xe)
/usr/local/go/src/runtime/panic.go:617 +0x72This indicates a goroutine's stack grew beyond the limit, usually due to unbounded recursion.
Common Scenarios and Solutions
Scenario 1: Infinite Recursion
Problem code: ```go func factorial(n int) int { return n * factorial(n - 1) // No base case! }
func main() { factorial(5) // Runs forever, stack grows until overflow } ```
Solution - Add proper base case: ```go func factorial(n int) int { if n <= 1 { return 1 // Base case stops recursion } return n * factorial(n - 1) }
func main() { fmt.Println(factorial(5)) // 120 } ```
Scenario 2: Deep Recursion on Large Input
Problem code: ```go func sumSlice(data []int) int { if len(data) == 0 { return 0 } return data[0] + sumSlice(data[1:]) // Creates new slice each call }
func main() { numbers := make([]int, 10000000) // 10 million elements sumSlice(numbers) // Stack overflow! } ```
Solution - Use iteration instead: ```go func sumSlice(data []int) int { total := 0 for _, v := range data { total += v } return total }
// Or use recursion with accumulator and proper structure func sumSliceRecursive(data []int) int { return sumHelper(data, 0, 0) }
func sumHelper(data []int, index int, total int) int { if index >= len(data) { return total } return sumHelper(data, index+1, total+data[index]) } ```
Scenario 3: Tree Traversal Stack Overflow
Problem code: ```go type Node struct { Value int Children []*Node }
func (n *Node) Depth() int { if n == nil { return 0 }
maxChildDepth := 0 for _, child := range n.Children { depth := child.Depth() // Recursive call for each child if depth > maxChildDepth { maxChildDepth = depth } } return maxChildDepth + 1 }
// Very deep tree causes stack overflow ```
Solution - Use explicit stack (DFS): ```go func (n *Node) DepthIterative() int { if n == nil { return 0 }
type stackItem struct { node *Node depth int }
stack := []stackItem{{node: n, depth: 1}} maxDepth := 0
for len(stack) > 0 { current := stack[len(stack)-1] stack = stack[:len(stack)-1]
if current.depth > maxDepth { maxDepth = current.depth }
for _, child := range current.node.Children { stack = append(stack, stackItem{node: child, depth: current.depth + 1}) } }
return maxDepth } ```
Scenario 4: Mutual Recursion
Problem code: ```go func isEven(n int) bool { if n == 0 { return true } return isOdd(n - 1) }
func isOdd(n int) bool { if n == 0 { return false } return isEven(n - 1) }
func main() { isEven(1000000000) // Stack overflow } ```
Solution - Use iteration or modulus: ```go func isEven(n int) bool { return n % 2 == 0 }
func isOdd(n int) bool { return n % 2 != 0 } ```
Scenario 5: JSON Unmarshal Deep Nesting
Problem code:
``go
func main() {
// JSON with 10000 nested levels
data := buildDeepJSON(10000)
json.Unmarshal(data, &result) // May cause stack overflow
}
Solution - Limit nesting depth: ```go func parseJSONWithLimit(data []byte, maxDepth int) error { decoder := json.NewDecoder(bytes.NewReader(data))
depth := 0 for { token, err := decoder.Token() if err == io.EOF { break } if err != nil { return err }
switch token { case json.Delim('{'), json.Delim '[': depth++ if depth > maxDepth { return fmt.Errorf("JSON nesting exceeds limit of %d", maxDepth) } case json.Delim('}'), json.Delim ']': depth-- } }
// Now safely unmarshal return json.Unmarshal(data, &result) } ```
Scenario 6: String/Regexp Matching Stack Overflow
Problem code:
``go
func main() {
// Certain regex patterns cause catastrophic backtracking
pattern := regexp.MustCompile((a+)+b)
pattern.FindString("aaaaaaaaaaaaaaaaaaaac") // Stack/CPU explosion
}
Solution - Use atomic groups or simpler patterns:
``go
func main() {
// Use atomic group (possessive quantifier)
// Note: Go regex doesn't support atomic groups directly
// Use simpler pattern instead
pattern := regexp.MustCompile(a+b`)
pattern.FindString("aaaaaaaaaaaaaaaaaaaab") // Works fine
// Or validate input length first input := "aaaaaaaaaaaaaaaaaaaac" if len(input) > 100 { log.Fatal("Input too long") } } ```
Stack Size Management
Check and Set Stack Limits
```go func main() { // Get initial stack size var memStats runtime.MemStats runtime.ReadMemStats(&memStats) fmt.Printf("Initial stack size: %d\n", runtime.GOROOT())
// Go 1.4+ uses contiguous stacks that grow dynamically // Max stack size is 1 GB on 64-bit, 250 MB on 32-bit } ```
Use Larger Stack for Known Deep Recursion
```go func main() { // For known deep recursion, use goroutine with explicit stack done := make(chan int)
go func() { result := deepRecursiveFunction(10000) done <- result }()
result := <-done fmt.Println(result) } ```
Detecting Stack Issues
Debug Stack Usage
```go func monitorStack() { for { var buf [1024]byte n := runtime.Stack(buf[:], false) stack := string(buf[:n])
// Check stack size if len(stack) > 50000 { log.Println("Stack approaching limit!") log.Println(stack) }
time.Sleep(100 * time.Millisecond) } } ```
Catch Stack Overflow with recover
func safeDeepCall(fn func()) (err error) {
defer func() {
if r := recover(); r != nil {
if s, ok := r.(string); ok && strings.Contains(s, "stack overflow") {
err = errors.New("stack overflow detected")
} else {
panic(r) // Re-panic for other errors
}
}
}()
fn()
return nil
}Recursion Best Practices
Pattern 1: Convert to Iteration
```go // Recursive (limited stack) func fib(n int) int { if n <= 1 { return n } return fib(n-1) + fib(n-2) }
// Iterative (no stack limit) func fibIterative(n int) int { if n <= 1 { return n } a, b := 0, 1 for i := 2; i <= n; i++ { a, b = b, a+b } return b } ```
Pattern 2: Use Tail Recursion Pattern
```go // Not true tail recursion in Go, but clearer structure func factorialTail(n, acc int) int { if n <= 1 { return acc } return factorialTail(n-1, n*acc) }
func factorial(n int) int { return factorialTail(n, 1) } ```
Pattern 3: Manual Stack for Complex Recursion
```go func DFS(root *Node) { stack := []*Node{root}
for len(stack) > 0 { current := stack[len(stack)-1] stack = stack[:len(stack)-1]
// Process current process(current)
// Add children to stack for _, child := range current.Children { stack = append(stack, child) } } }
// BFS uses queue instead of stack func BFS(root *Node) { queue := []*Node{root}
for len(queue) > 0 { current := queue[0] queue = queue[1:]
process(current)
for _, child := range current.Children { queue = append(queue, child) } } } ```
Testing Stack Limits
```go func TestDeepRecursion(t *testing.T) { // Test that recursion handles expected depth maxDepth := 1000 // Expected maximum
result, err := safeDeepCall(func() { recursiveFunction(maxDepth) })
if err != nil { t.Errorf("Function should handle depth %d: %v", maxDepth, err) } } ```