Step 1 of 6

Recursion: a function that calls itself

A recursive function solves a problem by calling itself on a smaller version of the same problem. Every recursive function has two parts:

a base case: an input small enough to answer directly, without recursing;
a recursive case: shrink the problem, call yourself, and build the answer from the result.

fn factorial(n: u64) -> u64 {
    if n <= 1 {
        1 // base case
    } else {
        n * factorial(n - 1) // recursive case: a smaller problem
    }
}

fn countdown(n: u32) {
    if n == 0 {
        println!("liftoff!");
        return;
    }
    println!("{n}...");
    countdown(n - 1);
}

fn main() {
    println!("5! = {}", factorial(5));
    println!("20! = {}", factorial(20));
    countdown(3);
}

5! = 120
20! = 2432902008176640000
3...
2...
1...
liftoff!

The call stack

Each call gets its own stack frame holding its parameters and local variables. factorial(5) can't finish until factorial(4) returns, which waits for factorial(3), and so on: five frames stacked up, then unwinding as each returns its answer to the one below. The depth of recursion is how many frames pile up at once.

The stack is small (8 MB for the main thread on Linux) and Rust doesn't promise tail-call optimization (reusing the frame when the recursive call is the last thing a function does). Recursing a few hundred thousand levels deep crashes the program with thread 'main' (4242) has overflowed its stack. That's an abort, not a panic you can recover from. So:

Recursion is a great fit when the depth stays small: halving problems (depth log n), trees, nested folders, parsing nested expressions, trying choices.
For simple "do this for each of n items" work, use a loop or an iterator.

Recursion on slices

Slice patterns (from the patterns module) make recursive code on lists read like its definition: "the total of an empty list is 0; otherwise it's the first price plus the total of the rest":

fn total(prices: &[u32]) -> u32 {
    match prices {
        [] => 0,
        [first, rest @ ..] => first + total(rest),
    }
}

fn main() {
    println!("{}", total(&[250, 199, 1200]));
}

(This one is just for illustration: prices.iter().sum() is the idiomatic way, and doesn't use one stack frame per item.)

Common mistakes

No base case, or one the recursion never reaches. The calls never stop and the stack overflows. Rust even warns about some of these: function cannot return without recursing.
Not shrinking the problem. f(n) calling f(n) (or f(n + 1)) never reaches the base case.
Unsigned underflow. With u32/u64, a base case of n == 1 lets f(0) compute 0 - 1, which panics with attempt to subtract with overflow. Make the base case cover the smallest inputs.

Your task

Write fn sum_digits(n: u64) -> u64 recursively, without loops: the sum of the decimal digits of n (sum_digits(1234) is 10). The last digit is n % 10 and the rest of the number is n / 10; the sum of the digits of 0 is 0.

Challenge 2

Write fn is_palindrome(chars: &[char]) -> bool recursively with slice patterns, no loops: a slice with zero or one characters is a palindrome; a longer one is a palindrome if its first and last characters are equal and the middle part is a palindrome. The pattern [first, middle @ .., last] splits off both ends at once.

Challenge 3

Fast exponentiation. Hashing and cryptography need base to the power exp, modulo m, for exponents like 10^18. Multiplying exp times would take centuries. Recursion halves the exponent instead:

exp == 0: the answer is 1 % m
otherwise compute half = pow_mod(base, exp / 2, m); the answer is half * half % m, times one more base % m (then % m) if exp is odd

That's O(log exp) work: about 60 halvings (at most two multiplications each) for 10^18. Write fn pow_mod(base: u64, exp: u64, m: u64) -> u64. The modulus is between 1 and 1,000,000,007, so the product of two numbers below m fits in a u64. Reduce base with % m before multiplying, since it can be bigger than m.

Next: Branching recursion and backtracking