Why Factorial Using Recursion in DSA Rust?

The Big Idea

What if a simple function could solve a big multiplication puzzle by calling itself?

The Scenario

Imagine you want to find the factorial of a number, like 5! (which means 5 x 4 x 3 x 2 x 1). Doing this by hand means multiplying all numbers one by one, which can be slow and tiring for big numbers.

The Problem

Manually multiplying each number takes a lot of time and is easy to make mistakes, especially if the number is large. It's hard to keep track of all the steps and multiply correctly without missing any number.

The Solution

Using recursion, the computer breaks the problem into smaller parts automatically. It calculates the factorial by calling itself with smaller numbers until it reaches 0, then combines the results. This makes the code simple and easy to understand.

Before vs After

✗ Before

fn factorial(n: u32) -> u32 {
    let mut result = 1;
    for i in 1..=n {
        result *= i;
    }
    result
}

✓ After

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

What It Enables

Recursion lets us solve complex problems by breaking them into smaller, easier problems automatically.

Real Life Example

Calculating combinations in probability, where factorials help find how many ways to arrange or select items.

Key Takeaways

Manual multiplication is slow and error-prone for factorials.

Recursion simplifies the process by breaking it down into smaller calls.

This approach makes code cleaner and easier to maintain.

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