Rust Programming Language/

...

/

Recursion

Recursion

This lesson will get you acquainted with recursion in Rust.

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.

Press + to interact
// 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, ...