Recursive functions in Go are written by defining a function that calls itself with a modified argument, ensuring a base case exists to terminate the recursion and prevent stack overflow. Go does not enforce tail-call optimization, so deep recursion can exhaust the stack, making iterative solutions preferable for large datasets.
Here is a classic example calculating the factorial of a number:
func factorial(n int) int {
if n <= 1 {
return 1 // Base case
}
return n * factorial(n-1) // Recursive step
}
For traversing data structures like trees, recursion is often more readable than manual stack management. This example sums all values in a binary tree:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func sumTree(node *TreeNode) int {
if node == nil {
return 0 // Base case: empty node
}
return node.Val + sumTree(node.Left) + sumTree(node.Right)
}
When writing recursive logic, always verify that your base case is reachable and that the recursive call moves closer to that base case. If you need to process deep structures (e.g., thousands of nested items), convert the logic to an iterative approach using an explicit stack slice to avoid runtime panics.
func sumTreeIterative(root *TreeNode) int {
if root == nil {
return 0
}
stack := []*TreeNode{root}
sum := 0
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
sum += node.Val
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left != nil {
stack = append(stack, node.Left)
}
}
return sum
}
Use recursion for clean, readable code on shallow structures, but switch to iteration when performance or stack depth is a concern.