Factorial Using Recursion in DSA Rust - Build from Scratch

Factorial Using Recursion

📖 Scenario: Imagine you want to find the factorial of a number. Factorial means multiplying the number by all smaller numbers down to 1. For example, factorial of 4 is 4 x 3 x 2 x 1 = 24.

🎯 Goal: You will write a Rust program that calculates the factorial of a number using a function that calls itself (recursion). This helps understand how problems can be solved by breaking them into smaller parts.

📋 What You'll Learn

Create a variable called number with the value 5

Create a recursive function called factorial that takes an u32 and returns an u32

Use a base case in factorial to return 1 when the input is 0

Use recursion in factorial to multiply the number by factorial of number minus one

Print the result of factorial(number) with a message

💡 Why This Matters

🌍 Real World

Calculating factorials is useful in math, statistics, and computer science for permutations and combinations.

💼 Career

Understanding recursion is important for solving problems that can be broken down into smaller similar problems, common in software development and algorithm design.

1

Create the number variable

Create a variable called number and set it to 5.

DSA Rust

# Create a variable called number and set it to 5
# Your code here

Hint

Use let number: u32 = 5; inside the main function.

2

Write the factorial function

Write a recursive function called factorial that takes a parameter n of type u32 and returns u32. Use a base case to return 1 if n is 0.

DSA Rust

fn main() {
    let number: u32 = 5;
}

// Write the factorial function below
// Your code here

Hint

Use if n == 0 { 1 } else { n * factorial(n - 1) } inside the function.

3

Call factorial function with number

Inside the main function, create a variable called result and set it to the value returned by calling factorial(number).

DSA Rust

fn main() {
    let number: u32 = 5;
    // Create a variable result and set it to factorial(number)
    // Your code here
}

fn factorial(n: u32) -> u32 {
    if n == 0 {
        1
    } else {
        n * factorial(n - 1)
    }
}

Hint

Use let result = factorial(number); inside main.

4

Print the factorial result

Add a println! statement inside the main function to print: "Factorial of 5 is: {}" using the variable result.

DSA Rust

fn main() {
    let number: u32 = 5;
    let result = factorial(number);
    // Print the factorial result
    // Your code here
}

fn factorial(n: u32) -> u32 {
    if n == 0 {
        1
    } else {
        n * factorial(n - 1)
    }
}

Hint

Use println!("Factorial of 5 is: {}", result); to show the output.

Practice

1. What does the factorial of a number represent in mathematics?

easy

A. The number multiplied by 2

B. The sum of all positive integers up to that number

C. The number divided by 2

D. The product of all positive integers up to that number

Solution

1. Step 1: Understand factorial definition

   Factorial of a number n (written as n!) is the product of all positive integers from 1 to n.

2. Step 2: Compare options

   Only The product of all positive integers up to that number correctly describes factorial as a product, not sum or division.

3. Final Answer:

   The product of all positive integers up to that number -> Option D

4. Quick Check:

   Factorial = product of integers [OK]

Hint: Factorial multiplies numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial divides the number
• Assuming factorial doubles the number

2. Which of the following is the correct Rust function signature for a recursive factorial function?

easy

A. fn factorial(n: String) -> u32

B. fn factorial(n: u32) -> String

C. fn factorial(n: u32) -> u32

D. fn factorial(n: i32) -> bool

Solution

1. Step 1: Identify input and output types

   Factorial takes a positive integer (u32) and returns a positive integer (u32).

2. Step 2: Match function signature

   fn factorial(n: u32) -> u32 matches input and output types correctly for factorial.

3. Final Answer:

   fn factorial(n: u32) -> u32 -> Option C

4. Quick Check:

   Input and output types match factorial [OK]

Hint: Factorial input/output are unsigned integers [OK]

Common Mistakes:

• Using String type for input or output
• Using signed integer when unsigned is better
• Returning bool instead of number

3. What is the output of this Rust code?

fn factorial(n: u32) -> u32 {
    if n == 0 { 1 } else { n * factorial(n - 1) }
}

fn main() {
    println!("{}", factorial(4));
}

medium

A. 120

B. 24

C. 16

D. 10

Solution

1. Step 1: Trace recursive calls for factorial(4)

   factorial(4) = 4 * factorial(3) factorial(3) = 3 * factorial(2) factorial(2) = 2 * factorial(1) factorial(1) = 1 * factorial(0) factorial(0) = 1 (base case)

2. Step 2: Calculate values bottom-up

   factorial(1) = 1 * 1 = 1 factorial(2) = 2 * 1 = 2 factorial(3) = 3 * 2 = 6 factorial(4) = 4 * 6 = 24

3. Final Answer:

   24 -> Option B

4. Quick Check:

   4! = 24 [OK]

Hint: Recall 4! = 24 from multiplication table [OK]

Common Mistakes:

• Confusing factorial with sum
• Forgetting base case returns 1
• Multiplying incorrectly in recursion

4. Identify the error in this Rust factorial function:

fn factorial(n: u32) -> u32 {
    if n == 1 { 1 } else { n * factorial(n - 1) }
}

medium

A. Base case should be n == 0, not n == 1

B. Function should return bool instead of u32

C. Recursive call should be factorial(n + 1)

D. Missing semicolon after return statement

Solution

1. Step 1: Check base case correctness

   Factorial base case is when n == 0, factorial(0) = 1. Using n == 1 misses factorial(0).

2. Step 2: Understand recursion impact

   If base case is n == 1, factorial(0) call will recurse infinitely causing stack overflow.

3. Final Answer:

   Base case should be n == 0, not n == 1 -> Option A

4. Quick Check:

   Base case at zero prevents infinite recursion [OK]

Hint: Base case for factorial is zero [OK]

Common Mistakes:

• Setting base case at 1 instead of 0
• Changing recursion direction incorrectly
• Ignoring missing semicolons (Rust warns)

5. How would you modify the recursive factorial function to handle large inputs without overflow in Rust?

hard

A. Use u128 type and add a check for input range to avoid overflow

B. Change return type to i32 and multiply normally

C. Remove recursion and use a loop with u8 type

D. Use f64 type and return floating-point factorial

Solution

1. Step 1: Understand overflow in factorial

   Factorial grows very fast; u32 overflows quickly. Using u128 allows larger values.

2. Step 2: Add input range check

   To prevent overflow, check input is within safe range before calculation.

3. Final Answer:

   Use u128 type and add a check for input range to avoid overflow -> Option A

4. Quick Check:

   Use larger integer type and validate input [OK]

Hint: Use bigger integer type and check input size [OK]

Common Mistakes:

• Using signed integers causing negative overflow
• Using floating-point loses precision
• Ignoring overflow checks