Recursion on Arrays and Strings in DSA Python

Mental Model

Recursion solves a problem by breaking it into smaller, similar problems until it reaches the simplest case.

Analogy: Like peeling an onion layer by layer until you reach the core, recursion processes arrays or strings one element at a time until nothing is left.

array: [1, 2, 3, 4, 5]
string: "hello"

Recursion starts at the first element and moves forward ->

[1] -> [2] -> [3] -> [4] -> [5] -> null

or

'h' -> 'e' -> 'l' -> 'l' -> 'o' -> null
↑ current position

Dry Run Walkthrough

Input: array: [1, 2, 3], sum all elements using recursion

Goal: Calculate the sum of all elements by breaking the problem into smaller parts

Step 1: Call sum on [1, 2, 3], split into 1 + sum([2, 3])

[1, 2, 3] -> waiting for sum([2, 3])

Why: We reduce the problem by taking the first element and asking for the sum of the rest

Step 2: Call sum on [2, 3], split into 2 + sum([3])

[2, 3] -> waiting for sum([3])

Why: Keep breaking down until only one element remains

Step 3: Call sum on [3], split into 3 + sum([])

[3] -> waiting for sum([])

Why: Base case is empty array, which returns 0

Step 4: Call sum on [], return 0

[] -> 0

Why: Empty array means no elements left, so sum is zero

Step 5: Return 3 + 0 = 3

sum([3]) = 3

Why: Add last element to sum of empty array

Step 6: Return 2 + 3 = 5

sum([2, 3]) = 5

Why: Add current element to sum of rest

Step 7: Return 1 + 5 = 6

sum([1, 2, 3]) = 6

Why: Add first element to sum of rest to get total

Result:

sum([1, 2, 3]) = 6

Annotated Code

DSA Python

from typing import List

def recursive_sum(arr: List[int]) -> int:
    if not arr:  # base case: empty array
        return 0
    return arr[0] + recursive_sum(arr[1:])  # sum first element + sum rest

if __name__ == "__main__":
    data = [1, 2, 3]
    result = recursive_sum(data)
    print(f"sum({data}) = {result}")

if not arr: # base case: empty array

stop recursion when array is empty

return arr[0] + recursive_sum(arr[1:]) # sum first element + sum rest

add first element to recursive sum of remaining elements

Output

sum([1, 2, 3]) = 6

Complexity Analysis

Time: O(n) because each element is visited once in the recursion

Space: O(n) due to call stack growing with each recursive call for n elements

vs Alternative: Iterative sum uses O(1) space and O(n) time; recursion is simpler to write but uses more memory

Edge Cases

empty array

returns 0 immediately without recursion

DSA Python

if not arr:  # base case: empty array

array with one element

returns that element as sum

DSA Python

return arr[0] + recursive_sum(arr[1:])  # sum first element + sum rest

When to Use This Pattern

When you need to process arrays or strings by breaking them down element by element, recursion is a natural fit because it handles one piece at a time and calls itself for the rest.

Common Mistakes

Mistake: Forgetting the base case causes infinite recursion and crash
Fix: Always include a base case that stops recursion, like empty array check

Mistake: Modifying the original array inside recursion causing unexpected results
Fix: Use slicing or pass indices to avoid changing the original data

Summary

Recursion on arrays and strings breaks the problem into smaller parts until a simple base case is reached.

Use recursion when you want to process elements one by one and combine results naturally.

The key insight is to handle one element and let recursion handle the rest, stopping when nothing is left.

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