---
title: "7.7 Introduction to recursion"
description: "Functions that call themselves: base cases, recursive cases, stack overflows, and when to prefer a loop."
url: "https://learnrust.net/chapter-7/introduction-to-recursion/"
last_updated: "2026-06-12"
---
# 7.7 Introduction to recursion
A function in Rust may call any function it can see, including, it turns out, itself. A function that calls itself is called **recursive**, and recursion is this chapter's last way to make code run repeatedly, the only one that needs no loop statement at all.
```rust
fn countdown(n: u32) {
println!("{n}");
if n > 0 {
countdown(n - 1);
}
}
fn main() {
countdown(3);
}
```
```
3
2
1
0
```
Walk it through. `main` calls `countdown(3)`, which prints 3 and calls `countdown(2)`, which prints 2 and calls `countdown(1)`... down to `countdown(0)`, which prints 0 and, with `0 > 0` false, *doesn't* call again. Then the calls finish in reverse order, each one returning to the `countdown` that called it, and finally to `main`.
Two parts make this work, and every correct recursive function has both. The **recursive case** is the branch that calls the function again, with an argument moved *toward* the finish (`n - 1` here). The **base case** is the input for which the function *doesn't* call itself (`n == 0` here), which is what ends the chain. A loop's condition and a base case are the same idea wearing different clothes: both answer "when do we stop?"
## When you forget the base case
A loop without an exit runs forever. A recursive function without a base case does something more dramatic. Here's one, distilled:
```rust
fn deeper(depth: u64) -> u64 {
deeper(depth + 1)
}
fn main() {
println!("{}", deeper(1));
}
```
The compiler sees the problem at compile time and says so:
```
warning: function cannot return without recursing
--> src/main.rs:1:1
|
1 | fn deeper(depth: u64) -> u64 {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot return without recursing
2 | deeper(depth + 1)
| ----------------- recursive call site
|
= help: a `loop` may express intention better if this is on purpose
= note: `#[warn(unconditional_recursion)]` on by default
```
Run it anyway and:
```
thread 'main' (2296939) has overflowed its stack
fatal runtime error: stack overflow, aborting
```
Here's why the failure mode is a crash rather than a hang. Every function call claims a small ledge of memory for its local variables and bookkeeping, and that ledge is only released when the call *returns*. A million unfinished calls means a million ledges, all held at once. The region they're carved from (called the stack) is a few megabytes, and when it's exhausted, the program is over. This is a **stack overflow**, and yes, the famous website is named after it. The full story of the stack, with diagrams, is lesson 8.2; for this lesson, "each unfinished call holds memory until it returns" is the load-bearing fact.
Note the limits of the compile-time warning: it fires only when *no* path avoids the recursive call. A function with a base case that's merely *unreachable* (wrong condition, wrong direction of travel) compiles in silence and overflows at runtime. The compiler checks that a base case exists, not that you'll ever get there; getting there is your half of the contract.
## Recursion or a loop?
Lesson [7.5](https://learnrust.net/chapter-7/for-loops-and-ranges/)'s quiz built `sum_to` with a for loop. Here it is recursively, side by side:
```rust
fn sum_to_loop(value: u32) -> u32 {
let mut sum = 0;
for i in 1..=value {
sum += i;
}
sum
}
fn sum_to_recursive(value: u32) -> u32 {
if value == 0 {
return 0; // base case
}
value + sum_to_recursive(value - 1) // recursive case
}
fn main() {
println!("{}", sum_to_loop(100));
println!("{}", sum_to_recursive(100));
}
```
```
5050
5050
```
Read the recursive one as a sentence: the sum to 100 is "100 plus the sum to 99," and the sum to 0 is 0. No mutable state, no counter; the definition *is* the computation. Anything a loop can do, recursion can do, and vice versa, so the choice between them is about clarity and cost.
For `sum_to`, the loop wins on both counts (the recursive version holds 100 unfinished calls to compute what a single accumulator could). Recursion wins when the problem itself is shaped like smaller copies of itself. The textbook specimen is the Fibonacci sequence, where each number is the sum of the previous two:
```rust
fn fibonacci(n: u64) -> u64 {
if n <= 1 {
return n; // base cases: fibonacci(0) = 0, fibonacci(1) = 1
}
fibonacci(n - 1) + fibonacci(n - 2)
}
fn main() {
for n in 0..10 {
print!("{} ", fibonacci(n));
}
println!();
}
```
```
0 1 1 2 3 5 8 13 21 34
```
The function is nearly a transcription of the mathematical definition, which is recursion's great charm. (It's also spectacularly wasteful here: `fibonacci(40)` recomputes `fibonacci(2)` tens of millions of times. A loop version is thousands of times faster. Chapter 19's tools make the fast version pretty, too; until then, enjoy this one as a *readable* specimen rather than a shippable one.) Recursion's real home turf, structures that branch like trees, arrives with the data types of later chapters.
> **For advanced readers**
>
> Some languages promise that a recursive call in tail position (the very last act of a function) reuses the caller's stack ledge instead of claiming a new one, making such recursion exactly as cheap as a loop. Rust deliberately makes no such promise: the optimizer *may* do it, but you can't rely on it, and a deeply recursive function may overflow in debug builds even if it's fine in release. So in Rust, deep recursion (thousands of calls) is a loop's job.
> **Best practice**
>
> Prefer iteration (a loop) when it's no less clear, which for simple counting and accumulating it always is. Reach for recursion when the problem is self-similar and the recursive version is plainly easier to read and reason about.
## Quiz time
**Question #1**
This is `countdown` with the print moved *below* the recursive call. What does `count(3)` print?
```rust
fn count(n: u32) {
if n > 0 {
count(n - 1);
}
println!("{n}");
}
fn main() {
count(3);
}
```
Show solution
```
0
1
2
3
```
Each call recurses *first* and prints on the way back out: `count(3)` can't print its 3 until `count(2)` has completely finished, and so on down. The deepest call (`count(0)`) prints first. Moving one line turned a countdown into a count-up, which is the question every recursion trace must answer: does the work happen on the way down, or on the way back up?
**Question #2**
Write a recursive function `factorial(n: u64) -> u64` returning n! (the product of 1 through n), where `factorial(0)` is defined as 1. `factorial(5)` should return 120.
Show solution
```rust
fn factorial(n: u64) -> u64 {
if n == 0 {
return 1; // base case
}
n * factorial(n - 1)
}
fn main() {
println!("{}", factorial(5));
println!("{}", factorial(10));
}
```
```
120
3628800
```
Same skeleton as `sum_to_recursive` with `*` for `+` and a base of 1 instead of 0 (the do-nothing value for multiplication). Note factorials outgrow even `u64` fast: `factorial(21)` would overflow, and lesson [4.4](https://learnrust.net/chapter-4/integer-overflow/) told you exactly how that ends in a debug build.
**Question #3**
One of these two programs prints `done`; the other dies with a stack overflow. Which is which, and why?
```rust
// Program A
fn shrink(n: i32) {
if n == 0 {
return;
}
shrink(n - 2);
}
fn main() {
shrink(8);
println!("done");
}
```
```rust
// Program B
fn shrink(n: i32) {
if n == 0 {
return;
}
shrink(n - 2);
}
fn main() {
shrink(7);
println!("done");
}
```
Show solution
Program A prints `done`; Program B overflows the stack. The functions are identical; the *arguments* aren't. From 8, stepping by 2, the sequence 8, 6, 4, 2, 0 lands exactly on the base case. From 7, it goes 7, 5, 3, 1, **-1**, stepping over 0 entirely, and there's no base case below it: the calls continue through -3, -5, ... until the stack runs out. The base case existed in both; only one execution path ever reached it. (A sturdier base case, `n <= 0`, fixes Program B, and writing base cases as "at or past the finish" rather than "exactly at the finish" is a good reflex in general.)
Next: stopping. Not the loop, the whole program, and the polite and impolite ways to do it.
## Sitemap
See the full [sitemap](https://learnrust.net/sitemap.md) for all pages.