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

↓

Call recursion on smaller array/string

↓

Combine current result with recursive call result

↓

Return combined result

↓

End

Recursion breaks the array or string into smaller parts, processes one element, then calls itself on the rest until a base case is reached.

Execution Sample

DSA C

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

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

Execution Table

Step	Operation	Array Segment	n	Return Value	Explanation
1	Call sumArray(arr, 3)	[1, 2, 3]	3	?	Start with full array
2	Check base case n==0	No	3	?	n is 3, not 0
3	Return arr[0] + sumArray(arr+1, 2)	[1, 2, 3]	3	1 + ?	Add first element 1 to recursive call
4	Call sumArray(arr+1, 2)	[2, 3]	2	?	Recursive call on rest
5	Check base case n==0	No	2	?	n is 2, not 0
6	Return arr[0] + sumArray(arr+1, 1)	[2, 3]	2	2 + ?	Add first element 2 to recursive call
7	Call sumArray(arr+1, 1)	[3]	1	?	Recursive call on rest
8	Check base case n==0	No	1	?	n is 1, not 0
9	Return arr[0] + sumArray(arr+1, 0)	[3]	1	3 + ?	Add first element 3 to recursive call
10	Call sumArray(arr+1, 0)	[]	0	0	Base case reached, return 0
11	Return 3 + 0	[3]	1	3	Sum is 3
12	Return 2 + 3	[2, 3]	2	5	Sum is 5
13	Return 1 + 5	[1, 2, 3]	3	6	Sum is 6
14	Final result	[1, 2, 3]	3	6	Recursion ends

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

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 11	After Step 12	Final
arr	[1,2,3]	[2,3]	[3]	[]	[]	[3]	[1,2,3]
n	3	2	1	0	0	1	3
Return Value	?	?	?	?	3	5	6

Key Moments - 3 Insights

Why does the function call sumArray(arr + 1, n - 1) instead of sumArray(arr, n - 1)?

Because arr + 1 moves the pointer to the next element, so the recursive call processes the smaller array excluding the first element. This is shown in steps 3, 6, and 9 where the array segment changes.

What is the base case and why is it necessary?

The base case is when n == 0, returning 0 (step 10). It stops recursion to prevent infinite calls and provides a simple answer to build upon.

How does the function combine results from recursive calls?

Each call adds the first element of its array segment to the result of the recursive call on the rest, as seen in steps 3, 6, 9, 11, and 12.

Visual Quiz - 3 Questions

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

A 0

B 3

C 5

D 6

💡 Hint

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

At which step does the base case occur?

A Step 9

B Step 12

C Step 10

D Step 14

💡 Hint

Look for the step where n == 0 and the function returns 0.

If the array was [4, 5] instead of [1, 2, 3], what would be the return value at step 13?

A 9

B 6

C 5

D 4

💡 Hint

Sum of 4 + 5 is 9, check how return values accumulate in the execution_table.

Concept Snapshot

Recursion on Arrays and Strings:
- Base case stops recursion (e.g., empty array).
- Process one element, then recurse on smaller array/string.
- Combine current element with recursive result.
- Example: sumArray(arr, n) = arr[0] + sumArray(arr+1, n-1).
- Recursion unwinds after base case returns.

Full Transcript

Recursion on arrays and strings works by breaking the problem into smaller parts. We check if the array size is zero (base case). If yes, we return a simple result like zero. Otherwise, we take the first element, then call the function again on the rest of the array. This continues until the base case is reached. Then, the results combine as the calls return. For example, summing an array adds the first element to the sum of the rest. The execution table shows each step, the current array segment, and the return values building up. Key points include why we move the array pointer forward and the importance of the base case to stop recursion.