Factorial Using Recursion in DSA Rust

Mental Model

A function calls itself with a smaller number until it reaches 1, then builds the answer back up.

Analogy: Imagine stacking blocks: to find the total height, you ask the block below for its height, and keep asking down until the bottom block, then add up all heights on the way back.

factorial(3)
  ↓
factorial(2)
  ↓
factorial(1)
  ↓
return 1
  ↑
return 2 * 1 = 2
  ↑
return 3 * 2 = 6

Dry Run Walkthrough

Input: Calculate factorial of 3

Goal: Find 3! = 3 x 2 x 1 = 6 using recursion

Step 1: Call factorial(3), which calls factorial(2)

factorial(3) -> factorial(2) -> ?

Why: We reduce the problem by one to reach the base case

Step 2: Call factorial(2), which calls factorial(1)

factorial(3) -> factorial(2) -> factorial(1) -> ?

Why: Keep reducing until base case 1

Step 3: factorial(1) returns 1 (base case)

factorial(3) -> factorial(2) -> 1

Why: Base case stops recursion

Step 4: factorial(2) returns 2 * 1 = 2

factorial(3) -> 2

Why: Multiply current number by result of smaller problem

Step 5: factorial(3) returns 3 * 2 = 6

6

Why: Final result is product of all numbers down to 1

Result:

6

Annotated Code

DSA Rust

fn factorial(n: u32) -> u32 {
    if n == 0 || n == 1 {
        return 1; // base case: factorial of 0 or 1 is 1
    }
    n * factorial(n - 1) // recursive call multiplying current n by factorial of n-1
}

fn main() {
    let num = 3;
    let result = factorial(num);
    println!("Factorial of {} is {}", num, result);
}

if n == 0 || n == 1 { return 1; }

stop recursion at base case for 0 and 1

n * factorial(n - 1)

recursive call multiplying current number by factorial of smaller number

Output

Factorial of 3 is 6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching 1

Space: O(n) due to the call stack holding n recursive calls

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to write and understand

Edge Cases

Input is 1

Returns 1 immediately as base case

DSA Rust

if n == 0 || n == 1 { return 1; }

Input is 0

Returns 1 immediately as base case

DSA Rust

if n == 0 || n == 1 { return 1; }

When to Use This Pattern

When a problem asks for a value defined by smaller versions of itself, use recursion to break it down step by step.

Common Mistakes

Mistake: Missing base case causes infinite recursion
Fix: Add a condition to stop recursion when n equals 0 or 1

Mistake: Not reducing the input in recursive call leads to infinite loop
Fix: Call factorial with n - 1 to move towards base case

Summary

Calculates factorial by calling itself with smaller numbers until reaching 1.

Use when a problem can be broken down into smaller identical problems.

The key is the base case that stops recursion and builds the answer back up.

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