Factorial Using Recursion in DSA Typescript - 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 Typescript

function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

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

Execution Table

Step	Call	n	Condition n<=1?	Action	Return Value	Stack Depth
1	factorial(4)	4	No	Call factorial(3)		1
2	factorial(3)	3	No	Call factorial(2)		2
3	factorial(2)	2	No	Call factorial(1)		3
4	factorial(1)	1	Yes	Return 1	1	4
5	factorial(2)	2	No	Return 2 * 1	2	3
6	factorial(3)	3	No	Return 3 * 2	6	2
7	factorial(4)	4	No	Return 4 * 6	24	1
8	End			All calls returned		0

💡 Recursion ends when n <= 1, then results multiply 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	After Step 7	Final
n	4	4	3	2	1	2	3	4	4
Return Value					1	2	6	24	24
Stack Depth	0	1	2	3	4	3	2	1	0

Key Moments - 3 Insights

Why does factorial(1) return 1 instead of calling factorial(0)?

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

How does the multiplication happen after the base case returns?

After factorial(1) returns 1 (Step 4), each previous call multiplies n by the returned value (Steps 5-7).

What does stack depth represent in recursion?

Stack depth shows how many calls are waiting to complete; it increases with each call and decreases as calls return (see variable_tracker).

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 its base case?

A Step 3

B Step 4

C Step 5

D Step 7

💡 Hint

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

If the input n was 3 instead of 4, what would be the final return value?

A 3

B 24

C 6

D 1

💡 Hint

Check the pattern of multiplication in execution_table and variable_tracker for n=4 and adjust 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 shows call layers
- Stops when base case reached

Full Transcript

This visualization shows how factorial is calculated using recursion. The function calls itself with n-1 until it reaches the base case where n is 1 or less. At that point, it returns 1. Then each previous call multiplies its n by the returned value from the deeper call. The execution table tracks each call, the condition check, and the return values as the recursion unwinds. The variable tracker shows how n, return values, and stack depth change step by step. Key moments clarify why the base case stops recursion and how multiplication happens after. The quiz tests understanding of return values, base case step, and effect of changing input.

Practice

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

easy

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

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

C. The number multiplied by 2

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

   Only the product of all positive integers up to that number correctly describes factorial as a product, not sum or other operations.

3. Final Answer:

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

4. Quick Check:

   Factorial = product of integers [OK]

Hint: Factorial means multiply all numbers down to 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Thinking factorial divides
• Mixing factorial with doubling

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

easy

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

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

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

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

Solution

1. Step 1: Identify factorial base case

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

2. Step 2: Check options

   Only if (n === 0) return 1; returns 1 when n is 0, which is correct base case for recursion.

3. Final Answer:

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

4. Quick Check:

   Base case: 0! = 1 [OK]

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

Common Mistakes:

• Returning 0 for base case
• Using wrong base condition
• Returning n+1 incorrectly

3. What is the output of this TypeScript code?

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

medium

A. 120

B. 10

C. 16

D. 24

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 D

4. Quick Check:

   4! = 24 [OK]

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

Common Mistakes:

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

4. Identify the error in this recursive factorial function:

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

medium

A. No error, output is 1

B. Infinite recursion for input 0

C. Syntax error due to missing semicolon

D. Returns 0 for input 0

Solution

1. Step 1: Analyze base case for input 0

   Base case triggers only when n === 1, so factorial(0) calls factorial(-1), then factorial(-2), and so on infinitely.

2. Step 2: Understand recursion behavior

   Without base case for 0, recursion never stops for input 0, causing infinite recursion (stack overflow).

3. Final Answer:

   Infinite recursion for input 0 -> Option B

4. Quick Check:

   Missing base case for 0 causes infinite recursion [OK]

Hint: Always include base case for 0 in factorial [OK]

Common Mistakes:

• Missing base case for 0
• Assuming 1 covers 0
• Ignoring negative inputs

5. How can you modify the recursive factorial function to handle negative inputs gracefully in TypeScript?

hard

A. Return 0 for all negative inputs inside recursion

B. Remove the base case and let recursion handle negatives

C. Add a check to return -1 for negative inputs before recursion

D. Use a loop instead of recursion for negatives

Solution

1. Step 1: Understand factorial domain

   Factorial is not defined for negative numbers, so function should handle negatives before recursion.

2. Step 2: Add input validation

   Adding a condition to return -1 (or error) for negative inputs prevents invalid recursion calls.

3. Final Answer:

   Add a check to return -1 for negative inputs before recursion -> Option C

4. Quick Check:

   Validate input before recursion to handle negatives [OK]

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

Common Mistakes:

• Ignoring negative inputs
• Letting recursion run on negatives
• Returning wrong values for negatives