In this lesson, you will learn how to identify recursive patterns that trigger stack overflows and how to refactor them using iterative loops to ensure memory safety.
The Stack Limit Problem
Every thread in Rust has a limited amount of memory allocated to its "stack" (usually 2MB or 8MB). When you call a function, Rust pushes a new "frame" onto this stack to store local variables and return addresses.
A stack overflow occurs when a recursive function calls itself too many times without finishing. Each call consumes a piece of the stack until there is no room left, causing the program to crash abruptly.
Identifying the Risk
Consider a simple recursive function meant to sum numbers:
fn sum_recursive(n: u64) -> u64 {
if n == 0 { 0 }
else { n + sum_recursive(n - 1) }
}
If you call sum_recursive(1_000_000), your program will likely crash with a stack overflow. Each sum_recursive call must stay in memory until the base case (n == 0) is finally reached, preventing the compiler from clearing the stack frames.
Refactoring to Iteration
To prevent this, you should replace unbounded recursion with iterative loops. Iteration reuses the same stack frame instead of creating a new one for every step.
Here is the memory-safe way to write the same logic:
fn sum_iterative(n: u64) -> u64 {
let mut total = 0;
for i in 1..=n {
total += i;
}
total
}
By using a for loop, we only keep a few variables on the stack regardless of whether n is 10 or 10,000,000. The memory usage remains constant, making your code significantly more robust.
When to be Careful
Always ask yourself: "Does this function depend on input size?" If a recursive algorithm processes data structure depths (like deep tree traversals) that you don't control, consider if an iterative approach using an explicit Vec as a manual stack on the heap could solve the problem instead of relying on the system stack.
Key Takeaway: Replace deep recursive patterns with iterative loops to keep your stack usage constant and prevent your program from crashing under load.