Recursion Base Case and Recursive Case in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the base case in recursion?

The base case is the condition that stops the recursion. It tells the function when to stop calling itself to avoid infinite loops.

beginner

What is the recursive case in recursion?

The recursive case is the part where the function calls itself with a smaller or simpler input, moving towards the base case.

intermediate

Why do we need both base case and recursive case in a recursive function?

We need the base case to stop the recursion and the recursive case to break the problem into smaller parts. Without either, the function may never stop or not solve the problem.

beginner

Consider this code snippet:

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

Identify the base case and recursive case.

Base case: if n == 0: return 1
Recursive case: return n * factorial(n-1)

beginner

What happens if a recursive function does not have a base case?

The function will keep calling itself forever, causing a stack overflow error because it never knows when to stop.

What does the base case in recursion do?

A Stops the recursion

B Calls the function again

C Increases the input size

D Creates a new function

The base case stops the recursion by providing a condition where the function no longer calls itself.

In the recursive case, the function usually calls itself with:

A A smaller or simpler input

B A larger input

C The same input

D No input

The recursive case calls the function with a smaller or simpler input to move towards the base case.

What will happen if a recursive function lacks a base case?

A It will run once and stop

B It will cause an infinite loop

C It will return zero

D It will throw a syntax error

Without a base case, the function keeps calling itself endlessly, causing an infinite loop or stack overflow.

Which part of this code is the recursive case?

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

A if n == 0: return 0

B def sum_to_n(n):

C return n + sum_to_n(n-1)

D return 0

The recursive case is where the function calls itself with a smaller input: sum_to_n(n-1).

Why is the base case important in recursion?

A To make the function faster

B To increase memory usage

C To call other functions

D To stop the recursion and prevent errors

The base case stops the recursion and prevents infinite calls that cause errors.

Explain in your own words what the base case and recursive case are in recursion.

Think about how a function knows when to stop and how it breaks the problem down.

Describe what would happen if a recursive function has no base case.

Imagine a loop that never ends.

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