Factorial Using Recursion in DSA Javascript - Execution Trace

Concept Flow - Factorial Using Recursion

Call factorial(n)

↓

Is n == 0 or 1?

Yes→Return 1

No↓

Call factorial(n-1)

↓

Multiply n * factorial(n-1)

↓

Return result

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

Execution Sample

DSA Javascript

function factorial(n) {
  if (n === 0 || n === 1) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(4));

Calculates factorial of 4 by calling itself with decreasing values until base case.

Execution Table

Step	Call	Argument n	Action	Return Value	Stack Depth	Visual Call Stack
1	factorial(4)	4	Calls factorial(3)		1	factorial(4)
2	factorial(3)	3	Calls factorial(2)		2	factorial(4) -> factorial(3)
3	factorial(2)	2	Calls factorial(1)		3	factorial(4) -> factorial(3) -> factorial(2)
4	factorial(1)	1	Base case reached, returns 1	1	4	factorial(4) -> factorial(3) -> factorial(2) -> factorial(1)
5	factorial(2)	2	Returns 2 * 1	2	3	factorial(4) -> factorial(3) -> factorial(2)
6	factorial(3)	3	Returns 3 * 2	6	2	factorial(4) -> factorial(3)
7	factorial(4)	4	Returns 4 * 6	24	1	factorial(4)
8	Main	-	Prints 24	24	0	-

💡 Recursion ends when base case n=1 is reached and all calls return their results.

Variable Tracker

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

Key Moments - 3 Insights

Why does the function call itself with n-1 instead of n?

Because factorial is defined as n * factorial(n-1), so the function reduces the problem size each time until it reaches the base case (see steps 1-4 in execution_table).

What happens when n reaches 1?

At n=1, the base case is reached and the function returns 1 without further recursion (see step 4 in execution_table). This stops the recursion from going infinitely.

How does the multiplication happen after the base case?

After the base case returns 1, each previous call multiplies its n by the returned value from factorial(n-1), building the final result step by step (see steps 5-7 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the return value of factorial(1)?

A 0

B 2

C 1

D Undefined

💡 Hint

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

At which step does the recursion start to return values back up the call stack?

A Step 5

B Step 4

C Step 1

D Step 8

💡 Hint

Look for the first step where 'Return Value' is filled and stack depth decreases.

If the base case was changed to n === 0 only, what would happen when calling factorial(1)?

A It would return 0

B It would return 1

C It would cause infinite recursion

D It would throw an error

💡 Hint

factorial(1) calls factorial(0) which is the base case and returns 1, then returns 1 * 1 = 1.

Concept Snapshot

function factorial(n) {
  if (n === 0 || n === 1) return 1;  // base case
  return n * factorial(n - 1);       // recursive call
}

- Calls itself with smaller n until base case
- Multiplies results back up the call stack
- Base case stops infinite recursion

Full Transcript

This visualization shows how the factorial function uses recursion. The function calls itself with n-1 until it reaches the base case where n is 0 or 1, returning 1. Then each call multiplies n by the returned value from the smaller call. The execution table tracks each call, argument, and return value, showing the call stack growing and shrinking. The variable tracker shows how n and return values change step by step. Key moments clarify why the function calls itself with n-1, what happens at the base case, and how multiplication happens after. The quiz tests understanding of return values, recursion return steps, and base case importance.

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 product 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 matches this definition exactly.

3. Final Answer:

   The product of all positive integers up to that number -> Option C

4. Quick Check:

   Factorial = product sequence [OK]

Hint: Factorial multiplies numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial doubles the number
• Mixing factorial with division

2. Which of the following is the correct base case for a recursive factorial function in JavaScript?

easy

A. if (n === 1) return n * factorial(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 base case for factorial

   Factorial of 0 is defined as 1, so base case should return 1 when n is 0.

2. Step 2: Check options for correct base case

   if (n === 0) return 1; returns 1 when n is 0, which is correct. Others either return wrong values or recursive calls.

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(0) is 1 [OK]

Common Mistakes:

• Returning 0 for factorial(0)
• Using recursive call in base case
• Confusing base case with recursive step

3. What will be the output of the following JavaScript code?

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(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 (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 A

4. Quick Check:

   4! = 24 [OK]

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

Common Mistakes:

• Adding instead of multiplying
• Stopping recursion too early
• Misunderstanding base case

4. Find the error in this recursive factorial function:

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n + 1);
}

medium

A. The base case should be n === 0, not n === 1

B. The recursive call should use n - 1, not n + 1

C. The function should return n + factorial(n - 1)

D. There is no error; the function is correct

Solution

1. Step 1: Analyze recursive call direction

   The function calls factorial(n + 1), which increases n, causing infinite recursion.

2. Step 2: Correct recursive call

   To reach base case, n should decrease by 1 each call: factorial(n - 1).

3. Final Answer:

   The recursive call should use n - 1, not n + 1 -> Option B

4. Quick Check:

   Recursion must move toward base case [OK]

Hint: Recursive calls must reduce n to base case [OK]

Common Mistakes:

• Increasing n in recursive call
• Wrong base case value
• Using addition instead of multiplication

5. Consider this modified factorial function that returns the factorial of n only if n is even, otherwise returns 0:

function evenFactorial(n) {
  if (n === 0) return 1;
  if (n % 2 !== 0) return 0;
  return n * evenFactorial(n - 2);
}
console.log(evenFactorial(6));

What is the output of this code?

hard

A. 48

B. 720

C. 0

D. 120

Solution

1. Step 1: Understand function behavior

   Function returns 0 if n is odd. For even n, it multiplies n by factorial of n-2 recursively.

2. Step 2: Calculate evenFactorial(6)

   evenFactorial(6) = 6 * evenFactorial(4) evenFactorial(4) = 4 * evenFactorial(2) evenFactorial(2) = 2 * evenFactorial(0) evenFactorial(0) = 1 (base case) So, 2 * 1 = 2 4 * 2 = 8 6 * 8 = 48

3. Final Answer:

   48 -> Option A

4. Quick Check:

   Product of even numbers down to 0 = 48 [OK]

Hint: Multiply even numbers down by 2 recursively [OK]

Common Mistakes:

• Calculating full factorial instead of even factorial
• Returning 0 for even inputs
• Ignoring base case for 0