Factorial Using Recursion in DSA Python - 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 n until it reaches 0 or 1, then returns 1 and multiplies back up.

Execution Sample

DSA Python

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(4))

Calculates factorial of 4 by recursive calls multiplying down to 1.

Execution Table

Step	Call	n	Condition (n==0 or n==1)	Return Value	Stack Depth	Action
1	factorial(4)	4	False		1	Calls factorial(3)
2	factorial(3)	3	False		2	Calls factorial(2)
3	factorial(2)	2	False		3	Calls factorial(1)
4	factorial(1)	1	True	1	4	Returns 1
5	factorial(2)	2	False	2 * 1 = 2	3	Returns 2
6	factorial(3)	3	False	3 * 2 = 6	2	Returns 6
7	factorial(4)	4	False	4 * 6 = 24	1	Returns 24
8	Main			24	0	Prints 24 and ends

💡 Recursion ends when n reaches 1, then returns multiply back up to initial call.

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 call itself with n-1 instead of n?

Because factorial(n) depends on factorial(n-1), so the function reduces the problem size step by step as shown in steps 1-4 in the execution_table.

What stops the recursion from going forever?

The base case condition 'if n == 0 or n == 1' returns 1 and stops further recursive calls, as seen in step 4.

How does the function calculate the final result after reaching the base case?

After reaching the base case, each call returns its result multiplied by n, unwinding the stack as shown in steps 5-7.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value when factorial(2) finishes?

A 2

B 1

C 6

D 24

💡 Hint

Check step 5 in the execution_table where factorial(2) returns.

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 condition 'n==0 or n==1' is True in the execution_table.

If we call factorial(3) instead of factorial(4), how many recursive calls will be made?

A 2

B 4

C 3

D 1

💡 Hint

Count the number of calls from n down to 1 as shown in the Stack Depth column.

Concept Snapshot

Factorial Using Recursion:
- Base case: if n == 0 or 1, return 1
- Recursive case: return n * factorial(n-1)
- Calls stack up until base case, then multiply back
- Stack depth shows recursion levels
- 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. Then each call returns its result multiplied by n, unwinding the recursion stack. The execution table tracks each call, condition check, return value, and stack depth. The variable tracker shows how n and return values change at each step. Key moments clarify why recursion stops and how results build up. The quiz tests understanding of return values, base case, and call counts.

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

   Only The product of all positive integers up to that number correctly states this product definition.

3. Final Answer:

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

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 Python?

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 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 == 0, which is correct. Others return wrong values.

3. Final Answer:

   if n == 0: return 1 -> Option D

4. Quick Check:

   Base case n=0 returns 1 [OK]

Hint: Base case factorial(0) = 1 [OK]

Common Mistakes:

• Returning 0 for factorial(0)
• Using wrong base case condition
• Returning n+1 instead of 1

3. What is the output of the following code?

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(4))

medium

A. 10

B. 16

C. 24

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 C

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 causing infinite recursion

4. Find the error in this recursive factorial function:

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n+1)

print(factorial(3))

medium

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

B. The print statement should be outside the function

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

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

Solution

1. Step 1: Analyze recursive call parameter

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

2. Step 2: Correct recursive call to decrement n

   It should call factorial(n-1) to move towards base case and stop recursion.

3. Final Answer:

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

4. Quick Check:

   Recursion must approach base case by decreasing n [OK]

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

Common Mistakes:

• Increasing n in recursive call causing infinite loop
• Wrong base case value
• Adding instead of multiplying in return

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

hard

A. Change base case to n == -1

B. Add a check to return None or error if n < 0 before recursion

C. Use absolute value of n in recursive call

D. Ignore negative inputs and proceed as usual

Solution

1. Step 1: Understand factorial domain

   Factorial is not defined for negative numbers, so function should handle this case explicitly.

2. Step 2: Add input validation before recursion

   Check if n < 0 and return None or raise error to avoid invalid recursion.

3. Final Answer:

   Add a check to return None or error if n < 0 before recursion -> Option B

4. Quick Check:

   Validate input before recursion [OK]

Hint: Check for negative input before recursion [OK]

Common Mistakes:

• Using absolute value hides invalid input
• Changing base case to negative number
• Ignoring invalid inputs causes wrong results