Factorial Using Recursion in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this factorial function call?

Consider this Rust function that calculates factorial using recursion. What will be printed when calling factorial(4)?

DSA Rust

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

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

A 6

B 120

C 0

D 24

💡 Hint

Remember factorial of 4 is 4 * 3 * 2 * 1.

The factorial function multiplies n by factorial of n-1 until n is 0, where it returns 1. So factorial(4) = 4 * 3 * 2 * 1 = 24.

❓ Predict Output

intermediate

What is the output of factorial(0)?

Using the same factorial function, what will be printed when calling factorial(0)?

DSA Rust

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

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

A 1

B 0

C None

D Error

💡 Hint

Factorial of zero is defined as 1.

By definition, factorial(0) returns 1 as the base case in the recursion.

❓ Predict Output

advanced

What error occurs when calling factorial with a negative number?

Suppose we change the factorial function parameter to i32 and call factorial(-1). What happens?

DSA Rust

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

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

A Stack overflow error

B Compile time error

C Returns 1

D Returns 0

💡 Hint

Think about what happens when recursion never reaches base case.

Calling factorial(-1) causes infinite recursion because n never reaches 0, leading to stack overflow at runtime.

🧠 Conceptual

advanced

Why is recursion a good fit for factorial calculation?

Choose the best reason why recursion suits factorial calculation.

A Because recursion avoids all multiplication operations

B Because recursion uses less memory than loops

C Because factorial is defined in terms of itself (n * factorial(n-1))

D Because recursion always runs faster than iteration

💡 Hint

Think about how factorial is mathematically defined.

Factorial is naturally defined recursively, making recursion a direct and clear way to implement it.

❓ Predict Output

expert

What is the output of this tail-recursive factorial function?

Analyze this Rust code using tail recursion. What will be printed when calling factorial_tail(5, 1)?

DSA Rust

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

fn main() {
    println!("{}", factorial_tail(5, 1));
}

A 24

B 120

C 1

D 0

💡 Hint

Tail recursion uses an accumulator to carry the result.

The function multiplies acc by n each call, reducing n until zero, returning acc which holds factorial value.

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