Recursion
In this page:
A Simple Recursive Function
A recursive function is one that calls itself, typically with a smaller input, working toward a base case that stops further recursive calls.
Example: A Simple Recursive Function
fn factorial(n: u64) -> u64 {
if n == 0 {
1
} else {
n * factorial(n - 1)
}
}
fn main() {
println!("5! = {}", factorial(5));
}Login to try C/C++/Java/PHP code in the editor
The Base Case
Every correct recursive function needs a base case: a condition where it returns a value directly instead of recursing further. Without one, the function would call itself endlessly.
Example: The Base Case
fn countdown(n: i32) {
if n == 0 {
println!("Liftoff!");
return;
}
println!("{}", n);
countdown(n - 1);
}
fn main() {
countdown(3);
}Login to try C/C++/Java/PHP code in the editor
Recursion on a Naturally Recursive Structure
Some problems, like computing Fibonacci numbers, mirror a naturally recursive mathematical definition, making a recursive solution particularly clear even though each call spawns two more.
Example: Recursion on a Naturally Recursive Structure
fn fibonacci(n: u32) -> u64 {
if n < 2 {
n as u64
} else {
fibonacci(n - 1) + fibonacci(n - 2)
}
}
fn main() {
println!("fibonacci(10) = {}", fibonacci(10));
}Login to try C/C++/Java/PHP code in the editor
Recursion vs Iteration
Many recursive functions can be rewritten as loops, which avoid the risk of stack overflow on deep inputs. Choosing recursion is often about code clarity rather than raw performance.
Example: Recursion vs Iteration
fn factorial_iterative(n: u64) -> u64 {
let mut result = 1;
for i in 1..=n {
result *= i;
}
result
}
fn main() {
println!("5! (iterative) = {}", factorial_iterative(5));
}Login to try C/C++/Java/PHP code in the editor
- Forgetting to write a base case, causing the function to call itself forever until the program crashes with a stack overflow.
- Writing recursive solutions for problems better and more efficiently solved iteratively with a simple loop.
- Assuming Rust automatically optimizes tail-recursive calls into loops -- it does not guarantee tail-call optimization.
- A recursive function calls itself with a smaller or simpler input until it reaches a base case.
- Every recursive function needs at least one base case that stops the recursion.
- Deep recursion can exhaust the call stack; Rust does not guarantee tail-call optimization like some functional languages.
- Recursion is a natural fit for problems with a naturally recursive structure, like factorials or tree traversal.
Chapter Quiz — Complete all 6 topics to unlock
0/6 topics done
Complete these topics first: