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.

Practice

1. What does recursion mean when applied to arrays or strings?

easy

A. A function calls itself to solve smaller parts of the problem

B. A loop runs through all elements once

C. The array or string is sorted automatically

D. The data is copied to a new array or string

Solution

1. Step 1: Understand recursion concept

   Recursion means a function calls itself to break down a problem into smaller parts.

2. Step 2: Apply to arrays or strings

   For arrays or strings, recursion processes one element and then calls itself on the rest.

3. Final Answer:

   A function calls itself to solve smaller parts of the problem -> Option A

4. Quick Check:

   Recursion = function calls itself [OK]

Hint: Recursion always involves a function calling itself [OK]

Common Mistakes:

• Confusing recursion with loops
• Thinking recursion sorts data automatically
• Believing recursion copies data

2. Which of the following is the correct base case for a recursive function that processes a string?

easy

A. if (length < 0) return;

B. if (length == 0) return;

C. if (string == NULL) continue;

D. if (length > 0) return;

Solution

1. Step 1: Identify base case role

   The base case stops recursion when no more characters remain, usually length 0.

2. Step 2: Check options for correct base case

   if (length == 0) return; correctly returns when length is 0, stopping recursion safely.

3. Final Answer:

   if (length == 0) return; -> Option B

4. Quick Check:

   Base case stops recursion at empty string [OK]

Hint: Base case usually checks for empty string or zero length [OK]

Common Mistakes:

• Using incorrect base case conditions
• Using continue instead of return
• Checking for negative length which is invalid

3. What is the output of this C code?

void printReverse(char *str) {
  if (*str == '\0') return;
  printReverse(str + 1);
  printf("%c", *str);
}

int main() {
  char s[] = "abc";
  printReverse(s);
  return 0;
}

medium

A. cba

B. abc

C. Syntax error

D. No output

Solution

1. Step 1: Understand recursion flow

   The function calls itself moving forward in the string until it hits '\0' (end).

2. Step 2: Print characters on return

   After reaching end, it prints characters backward as recursion unwinds: 'c', 'b', 'a'.

3. Final Answer:

   cba -> Option A

4. Quick Check:

   Recursion prints string in reverse [OK]

Hint: Recursion with print after call reverses output [OK]

Common Mistakes:

• Expecting normal order output
• Confusing base case with print order
• Thinking code has syntax errors

4. Find the error in this recursive function that counts characters in a string:

int countChars(char *str) {
  if (*str == '\0')
    return 0;
  return 1 + countChars(str);
}

medium

A. Missing base case

B. Return type should be void

C. Recursive call does not move forward in string

D. Should use while loop instead

Solution

1. Step 1: Check base case correctness

   Base case correctly returns 0 when string ends.

2. Step 2: Analyze recursive call

   Recursive call uses same pointer 'str' without moving forward, causing infinite recursion.

3. Final Answer:

   Recursive call does not move forward in string -> Option C

4. Quick Check:

   Pointer must advance in recursion [OK]

Hint: Always move pointer forward in recursive calls on strings [OK]

Common Mistakes:

• Forgetting to advance pointer
• Changing return type unnecessarily
• Replacing recursion with loops without reason

5. You want to write a recursive function to check if a string is a palindrome (reads same forward and backward). Which approach is best?

hard

A. Count characters recursively and check if count is even

B. Reverse the string using recursion and compare with original

C. Use recursion to sort the string and compare with original

D. Compare first and last characters, then recurse on substring excluding them

Solution

1. Step 1: Understand palindrome check logic

   Palindrome means first and last characters must match, then check inside substring.

2. Step 2: Apply recursion on substring

   Recursively check smaller substring by removing first and last characters each time.

3. Final Answer:

   Compare first and last characters, then recurse on substring excluding them -> Option D

4. Quick Check:

   Check ends and recurse inside for palindrome [OK]

Hint: Check ends match, then recurse inside substring [OK]

Common Mistakes:

• Reversing string unnecessarily
• Counting characters instead of comparing ends
• Sorting string which changes order