Recursion Base Case and Recursive Case in DSA Python - Build from Scratch

Recursion Base Case and Recursive Case

📖 Scenario: Imagine you have a stack of books and you want to count how many books are in the stack. You can count them one by one, but you want to use a special method called recursion, which means the function calls itself to count the books.

🎯 Goal: You will build a recursive function called count_books that counts the number of books in a list by calling itself until it reaches the end of the list.

📋 What You'll Learn

Create a list called books with exactly these titles: 'Math', 'Science', 'History', 'Art'

Create a variable called index and set it to 0

Write a recursive function called count_books that takes books and index as parameters

In count_books, use a base case to stop recursion when index is equal to the length of books

In count_books, use the recursive case to return 1 + count_books(books, index + 1)

Print the result of calling count_books(books, index)

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like searching files in folders, solving puzzles, and processing tree structures.

💼 Career

Understanding recursion helps in software development roles that involve algorithms, data processing, and problem solving.

1

Create the list of books

Create a list called books with these exact titles: 'Math', 'Science', 'History', 'Art'

DSA Python

# Create the list of books
# Your code here

Hint

Use square brackets [] to create a list and separate the titles with commas.

2

Create the index variable

Create a variable called index and set it to 0

DSA Python

books = ['Math', 'Science', 'History', 'Art']
# Create the index variable
# Your code here

Hint

Use = to assign the value 0 to the variable index.

3

Write the recursive function

Write a recursive function called count_books that takes books and index as parameters. Use a base case to return 0 when index is equal to the length of books. Otherwise, return 1 + count_books(books, index + 1).

DSA Python

books = ['Math', 'Science', 'History', 'Art']
index = 0

# Write the recursive function count_books
# Your code here

Hint

The base case stops the recursion when index reaches the length of the list. The recursive case counts one book and calls itself with the next index.

4

Print the result of the recursive function

Print the result of calling count_books(books, index)

DSA Python

books = ['Math', 'Science', 'History', 'Art']
index = 0

def count_books(books, index):
    if index == len(books):
        return 0
    else:
        return 1 + count_books(books, index + 1)

# Print the count of books
# Your code here

Hint

Use print() to show the result of the recursive function call.

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