Recursion Base Case and Recursive Case in DSA Python - Time & Space Complexity

Time Complexity: Recursion Base Case and Recursive Case

O(n)

Understanding Time Complexity

When using recursion, it is important to understand how many times the function calls itself.

We want to know how the number of calls grows as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code calculates the factorial of a number using recursion with a base case and a recursive case.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The recursive call to factorial(n - 1).
• How many times: It repeats once for each number from n down to 1, so n times.

How Execution Grows With Input

Each time the function calls itself with a smaller number until it reaches zero.

Input Size (n)	Approx. Operations
10	About 10 recursive calls
100	About 100 recursive calls
1000	About 1000 recursive calls

Pattern observation: The number of calls grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows in a straight line as the input number gets bigger.

Common Mistake

[X] Wrong: "Recursion always takes exponential time because it calls itself multiple times."

[OK] Correct: In this example, the function calls itself only once per step, so the time grows linearly, not exponentially.

Interview Connect

Understanding how base and recursive cases affect time helps you explain your code clearly and shows you know how recursion works efficiently.

Self-Check

"What if the recursive case called the function twice instead of once? How would the time complexity change?"

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