Recursion Base Case and Recursive Case in DSA Python

Mental Model

Recursion solves a problem by calling itself with smaller parts until it reaches a simple case it knows how to solve directly.

Analogy: Imagine a set of nested boxes. To open the biggest box, you open the smaller box inside it, and keep opening smaller boxes until you find the smallest box that you can open easily without any more boxes inside.

big_box -> smaller_box -> smallest_box [base case]
↑ current box to open

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find 3! = 3 x 2 x 1 by breaking it down into smaller factorials until reaching 1

Step 1: Call factorial(3), not base case, so call factorial(2)

factorial(3) -> factorial(2) ↑ waiting for result

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

Step 2: Call factorial(2), not base case, so call factorial(1)

factorial(3) -> factorial(2) -> factorial(1) ↑ waiting for result

Why: Keep breaking down until we reach the simplest case

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

factorial(1) returns 1

Why: Base case stops recursion and starts returning answers

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

factorial(2) returns 2

Why: Combine smaller result with current step

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

factorial(3) returns 6

Why: Combine all results to get final answer

Result:

factorial(3) = 6

Annotated Code

DSA Python

def factorial(n: int) -> int:
    # Base case: if n is 1, stop recursion and 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 if we reached the simplest problem that can be solved directly

return 1

Return the answer for the base case to stop recursion

return n * factorial(n - 1)

Call the function itself with smaller input and combine the result

Output

factorial(3) = 6

Complexity Analysis

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

Space: O(n) because each recursive call adds a layer to the call stack until base case

vs Alternative: Compared to iterative approach which uses O(1) space, recursion uses more memory but is easier to write and understand for problems like factorial

Edge Cases

Input n = 1 (smallest valid input)

Function immediately returns 1 without further calls

DSA Python

if n == 1:

Input n = 0 or negative (not handled in code)

Function will recurse infinitely or error; no guard for invalid input

DSA Python

No explicit guard; user must provide valid input

When to Use This Pattern

When a problem can be broken into smaller versions of itself and has a simple stopping point, use recursion with a base case and recursive case.

Common Mistakes

Mistake: Forgetting the base case causes infinite recursion and crashes
Fix: Always include a base case that stops recursion

Mistake: Base case returns wrong value or is unreachable
Fix: Make sure base case matches the simplest input and returns correct answer

Summary

Recursion solves problems by calling itself with smaller inputs until reaching a base case.

Use recursion when a problem naturally breaks down into smaller similar problems with a clear stopping point.

The base case stops recursion, and the recursive case breaks the problem down step by step.

Practice

1. What is the purpose of the base case in a recursive function?

easy

A. To stop the recursion and prevent infinite calls

B. To call the function again with a smaller input

C. To increase the input size for the next call

D. To print the result of the recursion

Solution

1. Step 1: Understand recursion basics

   Recursion works by calling itself repeatedly until a stopping condition is met.

2. Step 2: Identify the role of base case

   The base case stops further recursive calls to avoid infinite loops.

3. Final Answer:

   To stop the recursion and prevent infinite calls -> Option A

4. Quick Check:

   Base case = stop recursion [OK]

Hint: Base case stops recursion to avoid infinite loops [OK]

Common Mistakes:

• Confusing base case with recursive case
• Thinking base case calls recursion again
• Ignoring the need for a stopping condition

2. Which of the following is the correct syntax for a recursive function in Python that calculates factorial?

easy

A. def fact(n): return n * fact(n+1)

B. def fact(n): while n > 0: return n * fact(n-1)

C. def fact(n): if n == 1: return 0 else: return n + fact(n-1)

D. def fact(n): if n == 0: return 1 else: return n * fact(n-1)

Solution

1. Step 1: Check base case correctness

   def fact(n): if n == 0: return 1 else: return n * fact(n-1) uses if n == 0: return 1 which is correct for factorial base case.

2. Step 2: Check recursive call correctness

   def fact(n): if n == 0: return 1 else: return n * fact(n-1) calls fact(n-1) and multiplies by n, which matches factorial definition.

3. Final Answer:

   def fact(n): if n == 0: return 1 else: return n * fact(n-1) -> Option D

4. Quick Check:

   Correct base and recursive case = def fact(n): if n == 0: return 1 else: return n * fact(n-1) [OK]

Hint: Base case returns 1 for factorial; recursive case multiplies by n [OK]

Common Mistakes:

• Using while loop instead of recursion
• Wrong base case value
• Recursive call increasing n instead of decreasing

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

def countdown(n):
    if n == 0:
        return 'Done'
    else:
        print(n)
        return countdown(n-1)

countdown(3)

medium

A. 3 2 1 Done

B. 3 2 1

C. Done

D. 3 2 1 0 Done

Solution

1. Step 1: Trace the recursive calls and prints

   Function prints 3, then calls countdown(2), prints 2, calls countdown(1), prints 1, calls countdown(0).

2. Step 2: Base case returns 'Done'

   When n == 0, function returns 'Done' without printing 0.

3. Final Answer:

   3 2 1 -> Option B

4. Quick Check:

   Prints 3,2,1; base case returns 'Done' (not printed) [OK]

Hint: Print happens before recursive call; base case returns 'Done' [OK]

Common Mistakes:

• Expecting 0 to be printed
• Ignoring the need for a stopping condition
• Confusing print order

4. Identify the error in this recursive function that sums numbers from n down to 1:

def sum_n(n):
    if n == 1:
        return 1
    else:
        return n + sum_n(n+1)

medium

A. Base case condition is wrong

B. Missing return statement in base case

C. Recursive call increases n causing infinite recursion

D. Function should use a loop instead

Solution

1. Step 1: Analyze recursive call parameter

   The function calls sum_n(n+1), which increases n, moving away from base case.

2. Step 2: Understand effect on recursion

   Since n increases, base case n == 1 is never reached, causing infinite recursion.

3. Final Answer:

   Recursive call increases n causing infinite recursion -> Option C

4. Quick Check:

   Recursive call must reduce n to reach base case [OK]

Hint: Recursive calls must move toward base case by decreasing input [OK]

Common Mistakes:

• Increasing n instead of decreasing
• Wrong base case condition
• Ignoring infinite recursion risk

5. Given the recursive function below, what will be the output when calling mystery(4)? Explain why.

def mystery(n):
    if n <= 0:
        return 0
    else:
        return n + mystery(n-2)

hard

A. 6 (4 + 2 + 0)

B. 10 (4 + 3 + 2 + 1)

C. 4 (only the first call)

D. Error due to missing base case

Solution

1. Step 1: Trace recursive calls with n=4

   mystery(4) calls 4 + mystery(2), mystery(2) calls 2 + mystery(0), mystery(0) returns 0.

2. Step 2: Calculate sum from calls

   Sum is 4 + 2 + 0 = 6.

3. Final Answer:

   6 (4 + 2 + 0) -> Option A

4. Quick Check:

   Recursive case adds n and calls with n-2 until n ≤ 0 [OK]

Hint: Sum n and n-2 recursively until base case n ≤ 0 [OK]

Common Mistakes:

• Assuming all numbers from n down to 1 are added
• Missing base case for n ≤ 0
• Confusing decrement step