Recursion in Rust

Our first example demonstrates a classic recursive function for calculating factorials.

fn fact(n: u64) -> u64 {
    if n == 0 {
        1
    } else {
        n * fact(n - 1)
    }
}

fn main() {
    println!("{}", fact(7));

    // Closures can also be recursive, but this requires the
    // closure to be declared with a type annotation explicitly
    // before it's defined.
    let fib: Box<dyn Fn(u64) -> u64> = Box::new(|n| {
        if n < 2 {
            n
        } else {
            fib(n - 1) + fib(n - 2)
        }
    });

    println!("{}", fib(7));
}

This fact function calls itself until it reaches the base case of fact(0).

In Rust, closures can also be recursive, but this requires a slightly different approach. We need to use a Box<dyn Fn(u64) -> u64> to create a recursive closure. This is because the size of a recursive closure isn’t known at compile time, so we need to use dynamic dispatch.

To run the program, save it as recursion.rs and use rustc to compile it, then run the resulting binary:

$ rustc recursion.rs
$ ./recursion
5040
13

The output shows the factorial of 7 (5040) and the 7th Fibonacci number (13).

Rust’s strong type system and ownership rules make it a bit more verbose to create recursive closures compared to some other languages, but it provides strong guarantees about memory safety and prevents many common bugs.