Start learning free

LESSON 283 OF 414 · RECURSION

Recursion in Rust: Factorial as the First Example

Lesson O(n) Read the full explanation

In this video lesson we will learn about recursion, how recursive algorithms work and we will code a classic problem in recursive manner - Factorial:

Problem - Factorial:

Write a recursive function that given a non-negative integer n, returns the factorial of n, also denoted as n!

n! = 1 * 2 * 3 * ... * (n - 1) * n

Example:

Input: n = 5
Output: 120
Explanation: 5! = 1 * 2 * 3 * 4 * 5 = 120

Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 2
    Ctrl + Enter to check

    RUST · RECURSION

    Recursion in Rust, explained

    What recursion is

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

    • a base case, an input small enough to answer directly, with no further call;
    • a recursive case, which reduces the input toward the base case and combines the result of the smaller call into the answer.

    Without a base case the calls never stop. Without progress toward it, the same happens.

    The exercise: factorial

    The factorial of a non-negative integer n, written n!, is 1 * 2 * 3 * ... * n. So 5! = 120. The lesson asks for a recursive function factorial(n) with O(n) time and O(n) extra space.

    The definition already contains the recursion: n! = n * (n - 1)!. The factorial of 5 is 5 times the factorial of 4, which is 4 times the factorial of 3, and so on down to 0! = 1, the base case. By convention 0! is 1, and the recursion needs that value to bottom out.

    Step by step

    1. Handle the base case. If n == 0, return 1 at once.
    2. Handle the recursive case. Return Self::factorial(n - 1) * n as the final expression, with no return and no semicolon. The call uses Self:: because factorial is an associated function of Solution, with no self parameter.

    The solution in Rust

    impl Solution {
    fn factorial(n: i32) -> i32 {
        if n == 0 {
            return 1;
        }
        Self::factorial(n - 1) * n
    }
}

    How the calls unfold

    For n = 3, the calls go down until the base case answers, and then each call finishes on the way back up:

    factorial(3) = factorial(2) * 3
factorial(2) = factorial(1) * 2
factorial(1) = factorial(0) * 1
factorial(0) = 1

    Now the multiplications happen from the bottom: factorial(1) is 1 * 1 = 1, factorial(2) is 1 * 2 = 2, and factorial(3) is 2 * 3 = 6.

    All of these calls are alive at the same time while the deepest one runs, each holding its own n on the call stack. That explains the cost: there are n + 1 calls, each doing constant work, so the time is O(n), and the stack holds n + 1 frames at its deepest, so the extra space is O(n).

    Rust details

    • Early return and the final expression. The base case uses return 1; to leave the function early. The last line has no semicolon, so its value is the function's result.
    • Self::. Inside an impl block, a function without self is called through the type, as Self::factorial. Writing a bare factorial(...) does not compile.
    • Overflow. An i32 holds values up to 2,147,483,647, and 13! is larger than that. The lessons build with optimizations, where the multiplication wraps silently: factorial(12) returns 479001600, but factorial(13) returns 1932053504, not 6227020800. A debug build would panic with an overflow error instead. The same function written with i64 returns 6227020800 for 13.
    • No tail-call guarantee. Rust does not promise to turn recursion into a loop, so very deep recursion can use up the stack. Factorial overflows i32 long before that matters, but keep it in mind for other recursive functions.

    Common mistakes

    • Forgetting the base case. The calls never reach an answer, and the program keeps going until the stack runs out.
    • Not moving toward the base case. Calling Self::factorial(n) instead of Self::factorial(n - 1) repeats the same problem forever.
    • Negative input. The base case is exactly 0, so a negative n never reaches it by counting down. The problem promises n >= 0.
    • Using 0 as the base answer. 0! is 1. Returning 0 would make every product 0.
    • Writing Self::factorial(n - 1) * n; with a semicolon. The function would then return () instead of an i32, and the compiler reports a mismatched type.

    Testing

    • factorial(0) gives 1.
    • factorial(1) gives 1.
    • factorial(5) gives 120.
    • factorial(10) gives 3628800.

    Key takeaways

    • A recursive function needs a base case and a recursive case that moves toward it.
    • Each pending call occupies stack space, so recursion that goes n deep costs O(n) extra space.
    • In Rust, call associated functions with Self::, and watch for i32 overflow in growing products.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free