Learn/Rust/11. Recursion
Lesson 11 of 15
Sign in

Rust, lesson 11

Recursion

A recursive function calls itself to solve a smaller version of the same problem. It is a natural fit for anything that contains smaller copies of itself: nested folders, family trees, or a list that is "one item followed by a shorter list".

Base case and recursive case

Every recursive function needs two parts:

  1. A base case small enough to answer directly.
  2. A recursive case that shrinks the problem, calls itself, and uses the answer.

factorial(3) waits on factorial(2), which waits on factorial(1), which returns 1. The waiting calls then finish in reverse: 2 * 1 = 2, 3 * 2 = 6. Each call has its own n, stored on the . Without a base case, or if the input never gets smaller, the stack fills up and the program aborts with a stack overflow.

2 exercises to try what you just read.

Exercise 1

Digital root

Press Ctrl Enter or Check to test your code.

Exercise 2

Coin combinations

Press Ctrl Enter or Check to test your code.

call stack

Note that if/else is an expression here, so the function body is a single expression with no return needed.

Recursion over slices

Slices make "the rest of the list" cheap, and slice patterns in match make it pretty:

[] matches an empty slice. [first, rest @ ..] matches a slice with at least one element, binding the first element to first and the remaining slice to rest. No copying happens; rest is a view into the same data.

Branching recursion and memoisation

Some problems split into two or more sub-problems. The number of ways to climb n stairs taking 1 or 2 steps at a time is ways(n-1) + ways(n-2). Written directly, this recomputes the same values exponentially many times. Memoisation stores each answer the first time and reuses it:

The memo is passed down as &mut, a mutable borrow, so every call shares the same map.

Helper functions with extra parameters

Often the cleanest recursive design has a small public function that calls a helper with extra parameters, such as a current position or an accumulated result. For example, building all binary strings of length n uses a helper that carries the prefix so far:

This "choose, recurse, undo" shape is called backtracking.

Recursion or loops?

Rust does not guarantee tail-call optimisation, so a simple countdown is better as a loop. Use recursion when the problem branches or the data is tree-shaped; it often turns a tangle of loops into a few clear lines.

Further reading

  • The Rust Book: Functions
  • The Rust Reference: Slice patterns
  • Rust by Example: match destructuring arrays and slices

The digital root of a number comes from adding its digits, then adding the digits of the result, and so on until one digit remains. For 9875: 9+8+7+5 = 29, 2+9 = 11, 1+1 = 2.

Write a recursive fn digit_sum(n: u64) -> u64 (last digit is n % 10, the rest is n / 10) and a recursive fn digital_root(n: u64) -> u64 that uses it. Read one non-negative integer and print its digital root.

Sample input:

Sample output:

A vending machine accepts coins of a few values. Count how many different combinations of coins add up to an amount, where order does not matter (1+2 and 2+1 are the same combination).

The first line holds the amount. The second line holds the coin values (distinct, positive). Write a recursive fn count(amount: i64, coins: &[i64]) -> u64 using this idea: either use the first coin at least once (count(amount - coins[0], coins)), or never use it (count(amount, &coins[1..])). The base cases: amount 0 means one way (use nothing); a negative amount or no coins left means zero ways.

Sample input:

Sample output:

(The four ways are 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1.)

fn factorial(n: u64) -> u64 {
    if n <= 1 {
        1 // base case
    } else {
        n * factorial(n - 1) // smaller problem
    }
}
fn sum(nums: &[i64]) -> i64 {
    match nums {
        [] => 0,
        [first, rest @ ..] => first + sum(rest),
    }
}

println!("{}", sum(&[3, 4, 5])); // 12
use std::collections::HashMap;

fn ways(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if n <= 1 {
        return 1;
    }
    if let Some(&v) = memo.get(&n) {
        return v;
    }
    let v = ways(n - 1, memo) + ways(n - 2, memo);
    memo.insert(n, v);
    v
}
fn binary(prefix: &mut String, n: usize, out: &mut Vec<String>) {
    if prefix.len() == n {
        out.push(prefix.clone());
        return;
    }
    for bit in ['0', '1'] {
        prefix.push(bit);
        binary(prefix, n, out);
        prefix.pop(); // undo before trying the next choice
    }
}
9875
2
5
1 2 5
4