Factorial Using Recursion in DSA Rust - Execution Trace

Concept Flow - Factorial Using Recursion

Call factorial(n)

↓

Is n <= 1?

Yes→Return 1

No↓

Call factorial(n-1)

↓

Multiply n * factorial(n-1)

↓

Return result

The function calls itself with n-1 until it reaches 1, then returns 1 and multiplies back up.

Execution Sample

DSA Rust

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

Calculates factorial of n by calling itself with n-1 until base case 1 is reached.

Execution Table

Step	Call	Argument n	Condition n <= 1?	Return Value	Stack Depth
1	factorial(4)	4	No	-	1
2	factorial(3)	3	No	-	2
3	factorial(2)	2	No	-	3
4	factorial(1)	1	Yes	1	4
5	Return from factorial(2)	2	-	2 * 1 = 2	3
6	Return from factorial(3)	3	-	3 * 2 = 6	2
7	Return from factorial(4)	4	-	4 * 6 = 24	1

💡 Recursion ends when n <= 1, then returns 1 and multiplies back up the call stack.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
n	-	4	3	2	1	2	3	4
Return Value	-	-	-	-	1	2	6	24
Stack Depth	0	1	2	3	4	3	2	1

Key Moments - 3 Insights

Why does the function call itself multiple times before returning a value?

Because each call waits for the result of factorial(n-1) before it can multiply and return, as shown in steps 1 to 4 in the execution_table.

What happens when n reaches 1 in the recursion?

At step 4, the condition n <= 1 is true, so the function returns 1 without further recursive calls, starting the return phase.

How does the stack depth change during recursion?

Stack depth increases by 1 with each recursive call (steps 1 to 4) and decreases by 1 as each call returns (steps 5 to 7), as tracked in the variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value at step 6?

A 2

B 24

C 6

D 1

💡 Hint

Check the 'Return Value' column at step 6 in the execution_table.

At which step does the recursion reach its base case?

A Step 1

B Step 4

C Step 7

D Step 3

💡 Hint

Look for the step where 'Condition n <= 1?' is 'Yes' in the execution_table.

If the initial call was factorial(3) instead of factorial(4), what would be the final return value?

A 6

B 24

C 2

D 1

💡 Hint

Refer to the pattern of return values in the execution_table and variable_tracker for n=3.

Concept Snapshot

Factorial Using Recursion:
- Base case: if n <= 1, return 1
- Recursive case: return n * factorial(n-1)
- Calls stack up until base case, then multiply back
- Stack depth grows with calls, shrinks with returns
- Useful for problems defined by smaller subproblems

Full Transcript

This visualization shows how the factorial function uses recursion. The function calls itself with a smaller number until it reaches 1, the base case. At that point, it returns 1. Then each previous call multiplies its number by the returned value, building up the final factorial result. The execution table tracks each call, the argument, condition check, return value, and stack depth. The variable tracker shows how n and return values change step by step. Key moments clarify why recursion waits for results and how the stack depth changes. The quiz tests understanding of return values, base case, and effect of changing input.

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