Recursion on Arrays and Strings in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Sum of Array Elements

What is the output of the following code when called with arr = [1, 2, 3, 4] and index = 0?

DSA Python

def recursive_sum(arr, index):
    if index == len(arr):
        return 0
    return arr[index] + recursive_sum(arr, index + 1)

print(recursive_sum([1, 2, 3, 4], 0))

A 10

B 24

C 0

D TypeError

💡 Hint

Think about how the function adds each element starting from index 0 until the end.

The function adds elements from index 0 to the end recursively. 1+2+3+4 = 10.

❓ Predict Output

intermediate

Output of Recursive String Reverse

What is the output of the following code when called with s = 'code'?

DSA Python

def reverse_string(s):
    if s == '':
        return ''
    return reverse_string(s[1:]) + s[0]

print(reverse_string('code'))

A TypeError

B code

C edoc

D edco

💡 Hint

The function moves the first character to the end recursively.

The function calls itself with the string except the first character, then adds the first character at the end, effectively reversing the string.

🧠 Conceptual

advanced

Recursion Depth in Array Search

Consider a recursive function that searches for a target value in an array by checking one element per call. If the array has 1000 elements, what is the maximum recursion depth reached during the search?

A 500

B 1000

C 1001

D 999

💡 Hint

Each recursive call checks one element and moves to the next.

The recursion depth equals the number of elements checked in the worst case, which is 1000 for 1000 elements.

❓ Predict Output

advanced

Output of Recursive Palindrome Check

What is the output of the following code when called with s = 'racecar'?

DSA Python

def is_palindrome(s, start, end):
    if start >= end:
        return True
    if s[start] != s[end]:
        return False
    return is_palindrome(s, start + 1, end - 1)

print(is_palindrome('racecar', 0, len('racecar') - 1))

A IndexError

B False

C None

D True

💡 Hint

Check characters from both ends moving inward.

The function compares characters from start and end indices moving inward. 'racecar' is a palindrome, so it returns True.

🔧 Debug

expert

Identify the Error in Recursive Fibonacci

What error does the following code produce when calling fibonacci(5)?

DSA Python

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 3)

print(fibonacci(5))

A RecursionError

B TypeError

C 0

D 5

💡 Hint

Check the recursive calls and base cases carefully.

The function calls fibonacci(n - 3) without a base case for n < 0, causing infinite recursion and RecursionError.

Practice

1. What does a recursive function do when processing an array or string?

easy

A. It loops through the array or string without calling itself.

B. It creates a new array or string without using recursion.

C. It calls itself with a smaller part of the array or string until a base case is reached.

D. It only processes the first element and stops.

Solution

1. Step 1: Understand recursion basics

   A recursive function calls itself with a smaller input to solve a problem step-by-step.

2. Step 2: Apply to arrays or strings

   For arrays or strings, recursion processes smaller parts until it reaches a base case (like empty array or string).

3. Final Answer:

   It calls itself with a smaller part of the array or string until a base case is reached. -> Option C

4. Quick Check:

   Recursion = smaller input calls [OK]

Hint: Recursion breaks problem into smaller parts [OK]

Common Mistakes:

• Thinking recursion processes entire array at once
• Confusing recursion with loops
• Ignoring the base case

2. Which of the following is the correct base case for a recursive function that reverses a string s?

easy

A. if s == s[::-1]: return s

B. if s == None: return s

C. if len(s) > 0: return s

D. if len(s) == 0: return s

Solution

1. Step 1: Identify base case for recursion

   The base case stops recursion. For strings, empty string means no more characters to reverse.

2. Step 2: Check options

   if len(s) == 0: return s checks if string length is zero and returns it, which is correct base case.

3. Final Answer:

   if len(s) == 0: return s -> Option D

4. Quick Check:

   Base case = empty string check [OK]

Hint: Base case usually checks for empty input [OK]

Common Mistakes:

• Using wrong condition for base case
• Checking reversed string equality as base case
• Returning input without base case

3. What is the output of this Python code?

def sum_array(arr):
    if len(arr) == 0:
        return 0
    return arr[0] + sum_array(arr[1:])

print(sum_array([1, 2, 3, 4]))

medium

A. 1234

B. 10

C. 24

D. Error

Solution

1. Step 1: Understand recursion on array sum

   Function adds first element to sum of rest of array recursively until empty array returns 0.

2. Step 2: Calculate sum step-by-step

   sum_array([1,2,3,4]) = 1 + sum_array([2,3,4]) = 1 + 2 + sum_array([3,4]) = 1 + 2 + 3 + sum_array([4]) = 1 + 2 + 3 + 4 + sum_array([]) = 1+2+3+4+0 = 10

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Sum of [1,2,3,4] = 10 [OK]

Hint: Add first element + recursive sum of rest [OK]

Common Mistakes:

• Concatenating numbers instead of adding
• Forgetting base case returns 0
• Misunderstanding slicing arr[1:]

4. Find the error in this recursive function that checks if a string is a palindrome:

def is_palindrome(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

print(is_palindrome('racecar'))

medium

A. The slicing s[1:-1] is correct and no error exists

B. The function will cause infinite recursion

C. The base case should check for len(s) == 0 only

D. The comparison s[0] != s[-1] is incorrect

Solution

1. Step 1: Analyze base case and recursion

   Base case checks if string length is 1 or 0, which is correct for palindrome check.

2. Step 2: Check slicing and comparison

   Slicing s[1:-1] removes first and last characters correctly. Comparison s[0] != s[-1] correctly detects mismatch.

3. Final Answer:

   The slicing s[1:-1] is correct and no error exists -> Option A

4. Quick Check:

   Correct base case and slicing = no error [OK]

Hint: Check base case and slicing carefully [OK]

Common Mistakes:

• Thinking base case must be only empty string
• Assuming slicing causes infinite recursion
• Misreading character comparison

5. Given a list of strings, write a recursive function to return a new list containing only the strings that start with the letter 'a'. Which of these recursive approaches is correct?

hard

A. Check first string; if it starts with 'a', include it and recurse on rest; else recurse on rest without including it.

B. Loop through list and add strings starting with 'a' without recursion.

C. Return the original list without filtering.

D. Check last string only and ignore the rest.

Solution

1. Step 1: Understand recursive filtering

   Recursion should process one element and decide to include it or not, then recurse on the rest.

2. Step 2: Apply to strings starting with 'a'

   If first string starts with 'a', include it in result list plus recursive call on rest; else skip it and recurse on rest.

3. Final Answer:

   Check first string; if it starts with 'a', include it and recurse on rest; else recurse on rest without including it. -> Option A

4. Quick Check:

   Recursive filter = check first + recurse rest [OK]

Hint: Include first if matches, else skip, then recurse [OK]

Common Mistakes:

• Using loops instead of recursion
• Ignoring elements except last
• Returning unfiltered list