Rust, lesson 11
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".
Every recursive function needs two parts:
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.
Note that if/else is an expression here, so the function body is a single expression
with no return needed.
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.
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.
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.
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.
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])); // 12use 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
}
}987525
1 2 54