Factorial Using Recursion in DSA Java - Execution Trace

Concept Flow - Factorial Using Recursion

Call factorial(n)

↓

Is n == 0 or 1?

Yes→Return 1

No↓

Return n * factorial(n-1)

↓

Recursive call with n-1

↓

Repeat until base case

↓

Unwind stack, multiply results

↓

Final factorial value returned

The function calls itself with smaller values until it reaches 0 or 1, then returns 1 and multiplies back up the call stack.

Execution Sample

DSA Java

int factorial(int n) {
  if (n == 0 || n == 1) return 1;
  return n * factorial(n - 1);
}

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

Execution Table

Step	Call	Argument n	Return Value	Stack Depth	Action
1	factorial(4)	4	pending	1	Check if n==0 or 1 (No), call factorial(3)
2	factorial(3)	3	pending	2	Check if n==0 or 1 (No), call factorial(2)
3	factorial(2)	2	pending	3	Check if n==0 or 1 (No), call factorial(1)
4	factorial(1)	1	1	4	Base case reached, return 1
5	factorial(2)	2	2	3	Return 2 * 1 = 2
6	factorial(3)	3	6	2	Return 3 * 2 = 6
7	factorial(4)	4	24	1	Return 4 * 6 = 24
8	End	-	-	0	All calls returned, final result 24

💡 Recursion ends when base case n==0 or n==1 is reached, then results multiply back up.

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	4	3	2	1	2	3	4
Return Value	pending	pending	pending	pending	1	2	6	24
Stack Depth	0	1	2	3	4	3	2	0

Key Moments - 3 Insights

Why does factorial(1) return 1 immediately?

Because factorial(1) is the base case (see Step 4 in execution_table), it stops recursion to avoid infinite calls.

How does the function multiply results back up after recursion?

Each call waits for factorial(n-1) to return, then multiplies n by that result (see Steps 5-7 in execution_table).

Why does the stack depth increase and then decrease?

Stack depth increases as recursive calls go deeper (Steps 1-4), then decreases as calls return results (Steps 5-8).

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value of factorial(2) at Step 5?

A 2

B 1

C 6

D 24

💡 Hint

Check the 'Return Value' column at Step 5 in execution_table.

At which step does the recursion reach the base case?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for the step where 'Return Value' is 1 and 'Action' says base case reached.

If the input n was 3 instead of 4, how many recursive calls would be made?

A 4

B 2

C 3

D 1

💡 Hint

Count the number of calls from n down to base case in execution_table steps.

Concept Snapshot

Factorial Using Recursion:
- Base case: if n==0 or n==1, return 1
- Recursive case: return n * factorial(n-1)
- Calls stack up until base case
- Then results multiply back down
- Stack depth shows recursion depth
- Stops when base case reached

Full Transcript

This visualization shows how factorial is calculated using recursion. The function calls itself with smaller values of n until it reaches the base case where n is 0 or 1, returning 1. Each recursive call waits for the next call to return, then multiplies n by that returned value. The stack depth increases as calls go deeper and decreases as they return. The final result is the factorial of the original n.

Practice

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

easy

A. The number multiplied by 2

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

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

D. The number divided by 2

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 with definition

   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 B

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 base case for a recursive factorial function in Java?

easy

A. if (n == 1) return n + 1;

B. if (n == 1) return 0;

C. if (n == 0) return 0;

D. if (n == 0) return 1;

Solution

1. Step 1: Identify factorial base case

   Factorial of 0 is defined as 1, so base case returns 1 when n == 0.

2. Step 2: Check options for correct base case

   Only if (n == 0) return 1; returns 1 when n == 0, others return incorrect values.

3. Final Answer:

   if (n == 0) return 1; -> Option D

4. Quick Check:

   Base case n=0 returns 1 [OK]

Hint: Base case for factorial is n=0 returns 1 [OK]

Common Mistakes:

• Returning 0 for base case
• Using n==1 with wrong return value
• Missing base case causing infinite recursion

3. What is the output of the following Java code?

public class Main {
  public static int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
  }
  public static void main(String[] args) {
    System.out.println(factorial(4));
  }
}

medium

A. 24

B. 10

C. 16

D. 120

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.

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 A

4. Quick Check:

   4! = 24 [OK]

Hint: Multiply down from n to 1 recursively [OK]

Common Mistakes:

• Adding instead of multiplying
• Wrong base case causing wrong output
• Confusing factorial(4) with sum

4. Find the error in this recursive factorial function:

public static int factorial(int n) {
  if (n == 1) return 1;
  return n * factorial(n);
}

medium

A. Return type should be void

B. Missing base case for n == 0

C. Recursive call uses same n causing infinite recursion

D. Multiplication operator is incorrect

Solution

1. Step 1: Analyze recursive call parameter

   The function calls factorial(n) again without reducing n, causing infinite recursion.

2. Step 2: Identify correct recursive call

   Recursive call should be factorial(n - 1) to reduce n and reach base case.

3. Final Answer:

   Recursive call uses same n causing infinite recursion -> Option C

4. Quick Check:

   Recursive call must reduce n [OK]

Hint: Recursive calls must reduce problem size [OK]

Common Mistakes:

• Calling factorial(n) instead of factorial(n-1)
• Missing base case for n=0
• Wrong return type

5. How would you modify the recursive factorial function to handle negative inputs by returning -1 for any negative number?

public static int factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n - 1);
}

hard

A. Add if (n < 0) return -1; before base case

B. Change base case to if (n <= 0) return 1;

C. Add if (n == 1) return -1; after base case

D. No change needed; factorial handles negatives

Solution

1. Step 1: Identify handling of negative inputs

   Factorial is undefined for negative numbers, so function should return -1 for n < 0.

2. Step 2: Add condition before base case

   Insert if (n < 0) return -1; before checking base case to catch negatives early.

3. Final Answer:

   Add if (n < 0) return -1; before base case -> Option A

4. Quick Check:

   Negative input returns -1 [OK]

Hint: Check negatives first, return error value [OK]

Common Mistakes:

• Changing base case incorrectly
• Not handling negatives causing infinite recursion
• Assuming factorial works for negatives