The crash that isn't a panic
You port a recursive tree traversal from Python to Rust. It handles a few nodes fine. Then you feed it a deep directory structure. The program vanishes with a segmentation fault. No panic message. No graceful exit. Just a crash.
Python developers expect recursion to work until memory runs out. Rust developers learn quickly that the call stack is a fixed resource. Rust does not protect you from stack overflows by default. The compiler trusts your logic. If your logic creates too many nested calls, the operating system terminates the process.
How the call stack fills up
Every function call consumes stack space. The CPU allocates a frame for local variables, arguments, and the return address. When the function returns, the frame is popped and the space is reclaimed. Recursion creates a chain of frames. Each level waits for the next level to finish.
Think of the call stack like a stack of index cards. Every time a function calls another, you write the current state on a new card and place it on top. When the function returns, you grab the top card, read the state, and continue. Rust gives you a desk with limited space. The default stack size is usually 2 megabytes on Linux and 1 megabyte on Windows. If your stack of cards grows taller than the ceiling, the cards fall everywhere. The operating system sees this mess and terminates your program immediately.
Minimal example: the silent killer
A simple recursive function looks safe. The base case exists. The logic is correct. The problem appears only when the input grows large.
/// Calculates factorial recursively.
/// WARNING: This will stack overflow for large n.
fn factorial(n: u64) -> u64 {
if n <= 1 {
return 1;
}
// Each call adds a frame to the stack.
// The frame holds n and the return address.
n * factorial(n - 1)
}
fn main() {
// 100_000 frames exceed the default stack size.
// The OS kills the process with SIGSEGV.
// No error message is printed.
println!("{}", factorial(100_000));
}
Run this code and the process dies. You might see stack overflow in the output if the panic handler manages to run, but often the signal arrives before Rust can print anything. The crash is brutal.
Rust won't catch this at compile time. The compiler cannot prove how deep the recursion goes for arbitrary input. The crash happens at runtime. You need a strategy to guard the stack.
What happens under the hood
When factorial(100_000) runs, the CPU allocates a frame for n=100_000. It calls factorial(99_999), allocating another frame. This repeats. After a few thousand calls, the stack pointer hits the memory limit.
Rust enables stack probing on many platforms. Probing inserts checks at the start of functions to detect if the stack is getting dangerously low. If probing detects a problem, it can trigger a panic instead of a segfault. This gives you a chance to handle the error. However, probing has overhead. It is not a magic shield. It just changes a segfault into a panic. You still need to limit depth.
The compiler assumes you know how deep you are going. Rust's safety guarantees protect memory safety. They do not protect against resource exhaustion like stack depth. Treat recursion depth as a resource limit, just like memory. Guard it explicitly.
Strategy 1: Depth limits with Result
The most common fix is to track the recursion depth and stop when it exceeds a safe threshold. Return a Result so the caller can handle the failure gracefully.
/// Public API for factorial.
/// Users don't see the depth counter.
pub fn factorial(n: u64) -> Result<u64, &'static str> {
// Start the recursion with depth 0.
factorial_inner(n, 0)
}
/// Internal recursive helper with depth tracking.
fn factorial_inner(n: u64, depth: u32) -> Result<u64, &'static str> {
// Hard limit prevents stack overflow.
// 1000 is arbitrary; tune based on your stack size and frame size.
if depth > 1000 {
return Err("Recursion depth exceeded");
}
if n <= 1 {
return Ok(1);
}
// Propagate errors from deeper calls.
let sub = factorial_inner(n - 1, depth + 1)?;
Ok(n * sub)
}
fn main() {
match factorial(5000) {
Ok(v) => println!("Result: {}", v),
Err(e) => eprintln!("Failed: {}", e),
}
}
Passing depth through every call clutters the API. The community convention is to hide the counter in a private helper function. The public function calls the helper with depth = 0. This keeps the interface clean. Users call factorial(n) and get a Result. They don't need to know about the internal safety mechanism.
Choose the threshold based on your stack size and the size of each frame. A frame with many local variables consumes more space. Test with realistic inputs. If your threshold is too low, you reject valid data. If it is too high, you risk a crash.
Wrap the recursion. Expose the clean function. Keep the safety logic internal.
Strategy 2: The iterative escape hatch
Recursion is convenient, but iteration is robust. You can rewrite any recursive algorithm as a loop with a manual stack. The manual stack lives on the heap. The heap has gigabytes of space. Your recursion limit becomes available RAM, not a few megabytes.
This approach guarantees constant stack usage. The call stack never grows beyond the depth of the loop function. It is the preferred solution for production systems handling arbitrary data.
#[derive(Debug)]
struct Node {
value: i32,
children: Vec<Node>,
}
/// Iterative depth-first traversal.
/// Uses a heap-allocated Vec for the stack.
fn traverse_iterative(root: &Node) -> Vec<i32> {
let mut result = Vec::new();
// Vec grows on the heap.
// No risk of stack overflow.
let mut stack = vec![root];
while let Some(node) = stack.pop() {
result.push(node.value);
// Push children in reverse order to maintain left-to-right processing.
// Stacks are LIFO, so reversing preserves order.
for child in node.children.iter().rev() {
stack.push(child);
}
}
result
}
fn main() {
let tree = Node {
value: 1,
children: vec![
Node { value: 2, children: vec![] },
Node { value: 3, children: vec![] },
],
};
println!("{:?}", traverse_iterative(&tree));
}
The code is slightly more verbose. You manage the stack explicitly. You push the work items and pop them in the loop. The logic is equivalent to recursion, but the memory usage is safe.
Factorial is easy to iterate with a simple loop. Real recursion often involves complex state. A tree traversal shows the pattern better. The manual stack holds the nodes you still need to visit. The loop processes them one by one. The stack grows on the heap. The call stack stays flat.
Move the stack to the heap. The heap has gigabytes of space. Your recursion limit becomes available RAM, not a few megabytes.
Strategy 3: Bigger stacks for stubborn recursion
Sometimes refactoring to iteration is impractical. The algorithm is inherently recursive. The depth is known to be large. You can spawn a new thread with a larger stack size. This isolates the heavy recursion in a separate thread. If it overflows, only that thread dies. The main thread survives.
use std::thread;
/// Deep recursive function that needs more stack.
fn deep_function(n: u64) -> u64 {
if n <= 1 {
return 1;
}
n * deep_function(n - 1)
}
fn main() {
// Spawn a thread with 64MB stack.
// Default is usually 2MB.
// 64 * 1024 * 1024 is clearer than a raw number.
let handle = thread::Builder::new()
.stack_size(64 * 1024 * 1024)
.spawn(|| {
// Deep recursion happens here.
// If it overflows, only this thread dies.
deep_function(100_000)
})
.expect("Failed to spawn thread");
// Wait for the thread to finish.
match handle.join() {
Ok(result) => println!("Result: {}", result),
Err(_) => eprintln!("Thread panicked or overflowed"),
}
}
The stack_size parameter is in bytes. Use multiplication to make the size readable. 64 * 1024 * 1024 is 64 megabytes. This gives you room for much deeper recursion.
This strategy is useful for parsing deeply nested structures or running algorithms with known high depth. It does not fix the root cause. It just gives you more buffer. If the input is unbounded, even 64 megabytes can run out. Combine this with a depth limit for safety.
Isolate the risk. Give the thread enough stack. Keep the main thread responsive.
Pitfalls and compiler behavior
Missing a base case causes infinite recursion. The compiler will not warn you. It trusts your logic. At runtime, you get a stack overflow. On Linux, this is signal 11 (SIGSEGV). On Windows, an access violation. The error message is usually just stack overflow in the panic output if the panic handler runs, but often the process dies before printing anything.
Rust does not guarantee tail call optimization. Python developers expect TCO. Rust does not provide it. The compiler might optimize some tail-recursive cases, but you cannot rely on it. If you write tail-recursive code expecting constant stack usage, you are gambling. Rewrite to a loop if you need guaranteed constant stack.
Using unsafe to manipulate the stack pointer directly is a bad idea. You bypass all safety checks. The program becomes undefined behavior. Never adjust the stack manually. Use the safe strategies above.
Treat recursion depth as a resource limit. Guard it explicitly. Verify your base cases. Test with deep inputs.
Decision matrix
Use a depth counter wrapped in a Result when the recursion depth correlates with input size and you can fail gracefully. This works well for parsing or tree traversal where inputs are usually shallow but could be malicious.
Use an iterative loop with a Vec as a manual stack when the depth is unbounded or you need guaranteed constant stack usage. This is the robust choice for production systems handling arbitrary data.
Use std::thread::spawn with a custom stack size when you must recurse deeply and refactoring to iteration is impractical. This isolates the heavy recursion in a separate thread with more stack space, protecting the main thread.
Reach for tail recursion only when you have verified via cargo asm or profiling that the compiler eliminated the call. Rust does not guarantee tail call optimization. Relying on it is a runtime risk.