Recursion on Arrays and Strings in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the sum of all elements in the array using recursion.

DSA Python

def recursive_sum(arr, n):
    if n == 0:
        return 0
    return arr[n-1] + recursive_sum(arr, [1])

Drag options to blanks, or click blank then click option'

An-1

Bn+1

Cn

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using n instead of n-1 causes infinite recursion.

Using n+1 goes beyond array bounds.

The function calls itself with one less element each time, so the correct argument is n-1.

2fill in blank

medium

Complete the code to check if a string is a palindrome using recursion.

DSA Python

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

Drag options to blanks, or click blank then click option'

Astart

Bstart - 1

Cend + 1

Dstart + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Moving start backward causes wrong comparisons.

Not moving start causes infinite recursion.

To check the next pair, move the start index forward by one.

3fill in blank

hard

Fix the error in the recursive function that counts occurrences of a target in an array.

DSA Python

def count_occurrences(arr, n, target):
    if n == 0:
        return 0
    count = count_occurrences(arr, n - 1, target)
    if arr[[1]] == target:
        count += 1
    return count

Drag options to blanks, or click blank then click option'

A0

Bn-1

Cn+1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using arr[n] causes index out of range error.

Using arr[0] always checks the first element only.

Array indices go from 0 to n-1, so accessing arr[n] is out of range. It should be arr[n-1].

4fill in blank

hard

Fill both blanks to create a recursive function that reverses a string.

DSA Python

def reverse_string(s):
    if len(s) == 0:
        return s
    return s[[1]] + reverse_string(s[[2]:-1])

Drag options to blanks, or click blank then click option'

A-1

B1

C0

D-2

Attempts:

3 left

💡 Hint

Common Mistakes

Using s[0] adds the first character repeatedly.

Using s[1:] excludes the first character, not the last.

The function takes the last character s[-1] and adds it to the reverse of the string excluding the last character s[0:-1].

5fill in blank

hard

Fill both blanks to create a dictionary of word lengths for words longer than 3 characters.

DSA Python

def word_lengths(words):
    return {word:[1]for word in words if len(word)[2]3}

Drag options to blanks, or click blank then click option'

A:

Blen(word)

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' includes short words.

Missing ':' causes syntax error.

The dictionary comprehension maps each word (key) to its length (value) for words longer than 3 characters.

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