Recursion on Arrays and Strings in DSA C++ - Execution Trace

Concept Flow - Recursion on Arrays and Strings

Start with full array/string

↓

Check base case: size == 0 or 1?

Yes→Return base result

No↓

Process current element or substring

↓

Call recursion on smaller array/string

↓

Combine current result with recursive call result

↓

Return combined result

Recursion breaks the array or string into smaller parts, processes one part, then calls itself on the smaller part until it reaches the base case.

Execution Sample

DSA C++

int sumArray(int arr[], int n) {
  if (n == 0) return 0;
  return arr[n-1] + sumArray(arr, n-1);
}

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

Execution Table

Step	Operation	Array Size (n)	Current Element arr[n-1]	Recursive Call Parameter	Partial Sum Returned	Visual State
1	Call sumArray(arr, 4)	4	4	sumArray(arr, 3)	-	[3, 2, 3, 4]
2	Call sumArray(arr, 3)	3	3	sumArray(arr, 2)	-	[3, 2, 3, 4]
3	Call sumArray(arr, 2)	2	2	sumArray(arr, 1)	-	[3, 2, 3, 4]
4	Call sumArray(arr, 1)	1	3	sumArray(arr, 0)	-	[3, 2, 3, 4]
5	Call sumArray(arr, 0) base case	0	-	-	0	[3, 2, 3, 4]
6	Return from sumArray(arr, 0)	0	-	-	0	[3, 2, 3, 4]
7	Return from sumArray(arr, 1)	1	3	-	3 + 0 = 3	[3, 2, 3, 4]
8	Return from sumArray(arr, 2)	2	2	-	2 + 3 = 5	[3, 2, 3, 4]
9	Return from sumArray(arr, 3)	3	3	-	3 + 5 = 8	[3, 2, 3, 4]
10	Return from sumArray(arr, 4)	4	4	-	4 + 8 = 12	[3, 2, 3, 4]

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 7	After Step 8	After Step 9	Final
n	4	4	3	2	1	0	1	2	3	4
Partial Sum	-	-	-	-	-	0	3	5	8	12

Key Moments - 3 Insights

Why does the recursion stop when n is 0?

Because the base case is defined as n == 0 (see step 5 in execution_table), which returns 0 and stops further recursive calls.

Why do we add arr[n-1] after the recursive call instead of before?

The recursive call sumArray(arr, n-1) computes the sum of the smaller array first (steps 2-6), then we add the current element arr[n-1] on returning (steps 7-10). This ensures all elements are included.

What happens if the array is empty?

If the array is empty, n is 0 at the start, so the base case immediately returns 0 without any recursive calls (step 5).

Visual Quiz - 3 Questions

Look at the execution_table, what is the partial sum returned at step 9?

A 5

B 8

C 12

D 3

💡 Hint

Check the 'Partial Sum Returned' column at step 9 in the execution_table.

At which step does the recursion hit the base case?

A Step 5

B Step 4

C Step 6

D Step 7

💡 Hint

Look for the step labeled 'base case' in the 'Operation' column of the execution_table.

If the array was [1, 2, 3], what would be the final partial sum returned?

A 7

B 5

C 6

D 3

💡 Hint

Sum of 1 + 2 + 3 = 6; relate to the final value in 'Partial Sum' in variable_tracker.

Concept Snapshot

Recursion on Arrays and Strings:
- Base case: smallest array/string (size 0 or 1)
- Process current element (e.g., arr[n-1])
- Recursive call on smaller array/string (n-1)
- Combine current element with recursive result
- Returns final combined result after all calls

Full Transcript

Recursion on arrays and strings works by breaking the problem into smaller parts. We check if the array size is zero, which is the base case to stop recursion. If not, we process the last element and call the function again on the smaller array. This continues until the base case is reached. Then, results combine as the calls return. For example, summing an array adds the last element to the sum of the rest recursively. The execution table shows each call and return step, tracking the current element and partial sums. Key moments include understanding the base case, order of addition, and handling empty arrays.

Practice

1. What does a recursive function on an array typically do to process the array elements?

easy

A. It processes one element and calls itself on the rest of the array

B. It processes all elements at once without calling itself

C. It uses loops instead of calling itself

D. It only processes the last element of the array

Solution

1. Step 1: Understand recursion on arrays

   A recursive function on an array usually handles one element and then calls itself on the remaining elements.

2. Step 2: Compare options

   It processes one element and calls itself on the rest of the array matches this behavior. Options A, C, and D describe non-recursive or incorrect methods.

3. Final Answer:

   It processes one element and calls itself on the rest of the array -> Option A

4. Quick Check:

   Recursion on arrays = process one element + recurse [OK]

Hint: Remember recursion breaks problem into smaller parts [OK]

Common Mistakes:

• Thinking recursion processes all elements at once
• Confusing recursion with loops
• Assuming recursion only processes last element

2. Which of the following is the correct base case for a recursive function that sums elements of an integer array arr of size n?

easy

A. if (n == 0) return 0;

B. if (n == 1) return arr[1];

C. if (arr == NULL) return 0;

D. if (n < 0) return 0;

Solution

1. Step 1: Identify base case for recursion on array size

   The base case should stop recursion when no elements are left, which is when n == 0.

2. Step 2: Check each option

   if (n == 0) return 0; returns 0 when n == 0, which is correct. if (n == 1) return arr[1]; incorrectly accesses arr[1] instead of arr[0]. if (arr == NULL) return 0; checks pointer but not size. if (n < 0) return 0; uses invalid negative size.

3. Final Answer:

   if (n == 0) return 0; -> Option A

4. Quick Check:

   Base case for empty array = return 0 [OK]

Hint: Base case usually when size is zero [OK]

Common Mistakes:

• Using wrong index in base case
• Checking pointer instead of size
• Allowing negative sizes

3. What is the output of the following C++ code?

int sumArray(int arr[], int n) {
  if (n == 0) return 0;
  return arr[n-1] + sumArray(arr, n-1);
}

int main() {
  int arr[] = {1, 2, 3, 4};
  int result = sumArray(arr, 4);
  std::cout << result;
  return 0;
}

medium

A. Compilation error

B. 24

C. 0

D. 10

Solution

1. Step 1: Trace recursive calls

   sumArray(arr,4) = arr[3] + sumArray(arr,3) = 4 + sumArray(arr,3) sumArray(arr,3) = arr[2] + sumArray(arr,2) = 3 + sumArray(arr,2) sumArray(arr,2) = arr[1] + sumArray(arr,1) = 2 + sumArray(arr,1) sumArray(arr,1) = arr[0] + sumArray(arr,0) = 1 + 0 = 1

2. Step 2: Calculate total sum

   Total = 4 + 3 + 2 + 1 = 10

3. Final Answer:

   10 -> Option D

4. Quick Check:

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

Hint: Sum recursion adds last element + sum of rest [OK]

Common Mistakes:

• Confusing index n-1 with n
• Forgetting base case returns 0
• Assuming sum is product

4. Find the error in this recursive function that counts occurrences of character c in string s:

int countChar(string s, char c, int index) {
  if (index == s.length()) return 0;
  if (s[index] == c) return 1 + countChar(s, c, index++);
  else return countChar(s, c, index++);
}

medium

A. Missing check for empty string

B. Base case condition is wrong

C. Using post-increment (index++) causes infinite recursion

D. Function should return bool, not int

Solution

1. Step 1: Analyze recursive calls with index++

   Using index++ passes the current index value before increment, so recursive call uses same index repeatedly.

2. Step 2: Identify infinite recursion cause

   Because index does not increase in recursive calls, base case is never reached, causing infinite recursion.

3. Final Answer:

   Using post-increment (index++) causes infinite recursion -> Option C

4. Quick Check:

   Post-increment in recursion argument = infinite loop [OK]

Hint: Use pre-increment (++index) or index+1 in recursion call [OK]

Common Mistakes:

• Using post-increment in recursive call argument
• Ignoring base case correctness
• Confusing return types

5. Given a string s, write a recursive function to check if it is a palindrome (reads same forward and backward). Which approach below correctly implements this?

hard

A. Reverse string using loop and compare with original

B. Check if first and last chars match, then recurse on substring excluding them

C. Count matching characters from start only

D. Use recursion to count characters and compare counts

Solution

1. Step 1: Understand palindrome check recursively

   To check palindrome recursively, compare first and last characters; if they match, recurse on substring excluding them.

2. Step 2: Evaluate options

   Check if first and last chars match, then recurse on substring excluding them matches this logic. Reverse string using loop and compare with original uses loops, not recursion. Options C and D do not correctly check palindrome property.

3. Final Answer:

   Check if first and last chars match, then recurse on substring excluding them -> Option B

4. Quick Check:

   Palindrome recursion = compare ends + recurse inside [OK]

Hint: Compare ends, recurse inside substring [OK]

Common Mistakes:

• Using loops instead of recursion
• Only checking one side of string
• Counting chars instead of comparing