Recursion on Arrays and Strings in DSA Python - Execution Trace

Concept Flow - Recursion on Arrays and Strings

Start with full array/string

↓

Check base case: empty or size 1?

Yes→Return base result

No↓

Process first element or last element

↓

Call recursion on smaller array/string

↓

Combine current element with recursive result

↓

Return combined result

Recursion breaks the array or string into smaller parts, solves the smallest part, then combines results back up.

Execution Sample

DSA Python

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

This code sums elements of an array recursively by adding the last element to the sum of the rest.

Execution Table

Step	Operation	Array State	n Value	Recursive Call	Return Value
1	Call sum_array(arr, 3)	[1, 2, 3]	3	sum_array(arr, 2)	pending
2	Call sum_array(arr, 2)	[1, 2, 3]	2	sum_array(arr, 1)	pending
3	Call sum_array(arr, 1)	[1, 2, 3]	1	sum_array(arr, 0)	pending
4	Call sum_array(arr, 0)	[1, 2, 3]	0	base case reached	0
5	Return from sum_array(arr, 0)	[1, 2, 3]	0	none	0
6	Calculate arr[0] + 0	[1, 2, 3]	1	none	1
7	Return from sum_array(arr, 1)	[1, 2, 3]	1	none	1
8	Calculate arr[1] + 1	[1, 2, 3]	2	none	3
9	Return from sum_array(arr, 2)	[1, 2, 3]	2	none	3
10	Calculate arr[2] + 3	[1, 2, 3]	3	none	6
11	Return from sum_array(arr, 3)	[1, 2, 3]	3	none	6

💡 Recursion stops when n reaches 0, the base case.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 6	After Step 8	After Step 10	Final
n	3	3	2	1	0	1	2	3	3
Return Value	none	pending	pending	pending	0	1	3	6	6

Key Moments - 3 Insights

Why does the recursion stop when n is 0?

Because step 4 shows the base case where n == 0 returns 0, stopping further recursive calls.

How does the function combine results from recursive calls?

At steps 6, 8, and 10, the function adds the current element arr[n-1] to the returned sum from the smaller array.

Why is the return value 'pending' during recursive calls?

Because the function waits for the recursive call to finish before it can calculate and return the sum, as seen in steps 1-3.

Visual Quiz - 3 Questions

Look at the execution table, what is the return value at step 6?

A 0

B 1

C 3

D 6

💡 Hint

Check the 'Return Value' column at step 6 in the execution_table.

At which step does the base case occur?

A Step 3

B Step 5

C Step 4

D Step 6

💡 Hint

Look for 'base case reached' in the 'Recursive Call' column.

If the array was empty, what would be the return value immediately?

A 0

B 1

C Array length

D Error

💡 Hint

Refer to the base case return value at step 4.

Concept Snapshot

Recursion on Arrays and Strings:
- Break problem into smaller parts
- Base case stops recursion (empty or size 0)
- Process one element and recurse on rest
- Combine results on return
- Useful for sums, searches, reversals

Full Transcript

Recursion on arrays and strings works by breaking the problem into smaller parts. The base case stops recursion when the array or string is empty or size zero. The function processes one element and calls itself on the smaller part. When the base case returns, results combine back up. For example, summing an array recursively adds the last element to the sum of the rest. The execution table shows each call and return, with the base case at n=0 returning zero. This method is useful for many problems like sums, searches, and reversals.

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