Recursion Base Case and Recursive Case in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Sum Function

What is the output of this recursive function when called with n = 4?

DSA Python

def recursive_sum(n):
    if n == 0:
        return 0
    else:
        return n + recursive_sum(n - 1)

print(recursive_sum(4))

A 24

B 0

C 10

D Error

💡 Hint

Think about how the function adds numbers from n down to 0.

The function adds n to the sum of all numbers below it until it reaches 0, which stops recursion. So, 4 + 3 + 2 + 1 + 0 = 10.

❓ Predict Output

intermediate

Output of Recursive Factorial Function

What is the output of this recursive factorial function when called with n = 3?

DSA Python

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

print(factorial(3))

A 3

B 6

C 9

D Error

💡 Hint

Factorial multiplies n by factorial of n-1 until it reaches 1.

factorial(3) = 3 * factorial(2) = 3 * 2 * factorial(1) = 3 * 2 * 1 = 6.

🔧 Debug

advanced

Identify the Error in Recursive Function

What error does this recursive function produce when called with n = 2?

DSA Python

def countdown(n):
    if n == 0:
        print('Blastoff!')
    else:
        print(n)
        countdown(n)

countdown(2)

A SyntaxError

B Prints 2, 1, Blastoff!

C Prints 2, 2, Blastoff!

D RecursionError: maximum recursion depth exceeded

💡 Hint

Check if the recursive call reduces the problem size.

The function calls countdown(n) without reducing n, causing infinite recursion and a RecursionError.

❓ Predict Output

advanced

Output of Recursive Fibonacci Function

What is the output of this recursive Fibonacci function when called with n = 5?

DSA Python

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(5))

A 5

B 8

C 3

D Error

💡 Hint

Fibonacci adds the two previous numbers starting from 0 and 1.

fibonacci(5) = fibonacci(4) + fibonacci(3) = 3 + 2 = 5.

🧠 Conceptual

expert

Understanding Base Case Importance

Why is the base case essential in a recursive function?

A It stops the recursion to prevent infinite calls.

B It makes the function run faster by skipping steps.

C It allows the function to call itself multiple times.

D It initializes variables before recursion starts.

💡 Hint

Think about what happens if recursion never stops.

The base case stops recursion by providing a condition to end recursive calls, preventing infinite loops.

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