Search⌘ K
Home
Courses
Rust Programming Language

Recursion

Explore the concept of recursion in Rust functions by understanding how a function can call itself with clear base and recursive cases. This lesson demonstrates recursion through factorial computation, helping you grasp how recursion operates and terminates in Rust programming.

We'll cover the following...

What Is Recursion?

Recursion is a method of function calling in which a function calls itself during execution.

There are problems which are naturally recursively defined. For instance, the factorial of a number nn is defined as n times the factorial of n−1n-1.

factorial(n) = n * factorial(n-1)

Parts of Recursion

In terms of programming, a recursive function must comprise two parts:

  • Base case

    A recursive function must contain a base case. This is a condition for the termination of execution.

  • Recursive case

    The function keeps calling itself again and again until the base case is reached.

Example

The following example computes the factorial of a number using recursion:

Note: A factorial is defined only for non-negative integer numbers.

Rust 1.40.0
// main function
fn main(){
    // call the function
    let n = 4;
    let fact = factorial(n);
    // print the factorial
    println!("factorial({}): {}", n, fact);
}
// define the factorial function
fn factorial(n: i64) -> i64 {
    if n == 0 { // base case
        1
    }
    else {
        n * factorial(n-1) // recursive case
    }
}

Explanation

  • main function

    The main function is defined from line 2 to line 7.

    • On line 4, a call is made to function factorial with an argument passed to the function and the return value is saved in the variable fact.

    • On line 6, ...