Factorial Using Recursion in DSA Python

Mental Model

A function calls itself with a smaller number until it reaches 1, then builds the answer back up.

Analogy: Imagine stacking blocks: to find the total height, you ask the block below for its height, and so on until the bottom block, then add up all heights.

factorial(3)
  ↓ calls factorial(2)
    ↓ calls factorial(1)
      ↓ returns 1
    ← returns 2 * 1 = 2
  ← returns 3 * 2 = 6

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find 3! = 3 x 2 x 1 = 6 by breaking it down into smaller factorial calls

Step 1: Call factorial(3), which calls factorial(2)

factorial(3) -> factorial(2) -> ?

Why: We reduce the problem to a smaller factorial to solve it step by step

Step 2: Call factorial(2), which calls factorial(1)

factorial(3) -> factorial(2) -> factorial(1) -> ?

Why: Keep breaking down until the base case is reached

Step 3: Call factorial(1), base case reached, return 1

factorial(1) returns 1

Why: Base case stops recursion and starts returning values

Step 4: factorial(2) returns 2 * factorial(1) = 2 * 1 = 2

factorial(2) returns 2

Why: Multiply current number by result of smaller factorial

Step 5: factorial(3) returns 3 * factorial(2) = 3 * 2 = 6

factorial(3) returns 6

Why: Multiply current number by result of smaller factorial to get final answer

Result:

factorial(3) = 6

Annotated Code

DSA Python

def factorial(n: int) -> int:
    # Base case: if n is 1, return 1
    if n == 1:
        return 1
    # Recursive case: multiply n by factorial of n-1
    return n * factorial(n - 1)

# Driver code to test factorial of 3
result = factorial(3)
print(f"factorial(3) = {result}")

if n == 1:

Check for base case to stop recursion

return 1

Return 1 when base case is reached

return n * factorial(n - 1)

Recursive call multiplying current n by factorial of n-1

Output

factorial(3) = 6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching 1

Space: O(n) due to the call stack holding n recursive calls

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to understand for factorial

Edge Cases

Input is 1

Returns 1 immediately as base case

DSA Python

if n == 1:

Input is 0 (not handled)

Function will not stop correctly, may cause infinite recursion or error

DSA Python

No explicit guard for 0 in code

When to Use This Pattern

When you see a problem that can be broken down into smaller versions of itself, think of recursion to solve it simply.

Common Mistakes

Mistake: Missing base case causes infinite recursion
Fix: Add a base case like 'if n == 1: return 1' to stop recursion

Mistake: Not reducing the problem size in recursive call
Fix: Make sure to call factorial(n - 1) to move towards base case

Summary

Calculates factorial of a number by calling itself with smaller numbers until reaching 1.

Use recursion when a problem can be divided into smaller identical problems.

The key is the base case that stops recursion and the recursive call that reduces the problem size.

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