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: empty or single element?

Yes→Return base result

No↓

Process first element

↓

Recursive call on rest of array/string

↓

Combine current element with recursive result

↓

Return combined result

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 index) {
  if (index == arr.Length) return 0;
  return arr[index] + SumArray(arr, index + 1);
}

This code sums all elements of an integer array recursively starting from index 0.

Execution Table

Step	Operation	Index	Current Element	Recursive Call	Return Value	Call Stack Depth
1	Check base case	0	1	SumArray(arr, 1)	?	1
2	Check base case	1	2	SumArray(arr, 2)	?	2
3	Check base case	2	3	SumArray(arr, 3)	?	3
4	Check base case	3	None (end)	Return 0	0	4
5	Return from recursion	2	3	None	3 + 0 = 3	3
6	Return from recursion	1	2	None	2 + 3 = 5	2
7	Return from recursion	0	1	None	1 + 5 = 6	1
8	Final return	0	1	None	6	0

💡 Index reaches array length 3, base case returns 0, recursion unwinds summing elements.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
index	0	1	2	3	3	2	1	0	0
Return Value	N/A	?	?	?	0	3	5	6	6
Call Stack Depth	0	1	2	3	4	3	2	1	0

Key Moments - 3 Insights

Why does the recursion stop when index equals array length?

Because the base case (Step 4) checks if index == arr.Length and returns 0 to stop further calls, as shown in execution_table row 4.

How does the function combine results during recursion?

Each return adds the current element to the result of the recursive call (see rows 5-7), building the sum as recursion unwinds.

Why is the call stack depth important here?

It shows how many recursive calls are active; depth increases going deeper (rows 1-4) and decreases as calls return (rows 5-8).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the return value?

A 0

B 3

C 6

D Undefined

💡 Hint

Check the 'Return Value' column at Step 4 where base case returns 0.

At which step does the recursion start to return values back up the call stack?

A Step 3

B Step 4

C Step 5

D Step 7

💡 Hint

Look for the first step where 'Return from recursion' appears in the Operation column.

If the array had one more element 4 at index 3, how would the call stack depth change at Step 4?

A It would be 4

B It would be 5

C It would be 3

D It would be 0

💡 Hint

Call stack depth increases by one for each recursive call before base case.

Concept Snapshot

Recursion on Arrays/Strings:
- Base case stops recursion (empty or end reached)
- Process one element per call
- Recursive call on rest of data
- Combine current element with recursive result
- Call stack grows with each call and shrinks on return

Full Transcript

This visualization shows how recursion works on arrays or strings by breaking the problem into smaller parts. The example sums an integer array recursively by processing one element at a time and calling itself on the rest. The base case stops recursion when the index reaches the array length. The execution table traces each step, showing the current index, element, recursive calls, return values, and call stack depth. Variable tracker shows how index and return values change. Key moments clarify why the base case is needed, how results combine, and the role of call stack depth. The quiz tests understanding of base case returns, recursion unwinding, and call stack size changes. The snapshot summarizes the recursion pattern for arrays and strings.

Practice

1. What is the main idea behind using recursion on arrays or strings?

easy

A. Sorting the array or string before processing

B. Using loops to iterate over each element

C. Breaking the problem into smaller similar problems until a base case is reached

D. Storing all elements in a new data structure

Solution

1. Step 1: Understand recursion concept

   Recursion solves problems by calling itself with smaller inputs until a simple base case is reached.

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:

   Breaking the problem into smaller similar problems until a base case is reached -> Option C

4. Quick Check:

   Recursion = divide and conquer [OK]

Hint: Think: solve small part, then repeat on smaller input [OK]

Common Mistakes:

• Confusing recursion with loops
• Ignoring the base case
• Trying to process all elements at once

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

easy

A. if (str[0] == '\0') return;

B. if (str == null) return;

C. if (str.Length > 0) return;

D. if (str.Length == 0) return;

Solution

1. Step 1: Identify base case for string recursion

   The base case should stop recursion when the string is empty (length zero).

2. Step 2: Check options

   if (str.Length == 0) return; correctly checks if string length is zero to stop recursion.

3. Final Answer:

   if (str.Length == 0) return; -> Option D

4. Quick Check:

   Base case = empty string check [OK]

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

Common Mistakes:

• Checking for null instead of empty string
• Using wrong condition like length > 0
• Checking for null character '\0' in C# strings

3. What will be the output of this C# recursive function call?

static int SumArray(int[] arr, int index) {
  if (index == arr.Length) return 0;
  return arr[index] + SumArray(arr, index + 1);
}

int[] nums = {1, 2, 3};
Console.WriteLine(SumArray(nums, 0));

medium

A. 6

B. 0

C. 3

D. StackOverflowException

Solution

1. Step 1: Trace recursive calls

   SumArray called with index 0 returns arr[0] + SumArray(1) = 1 + ... SumArray(1) returns 2 + SumArray(2) SumArray(2) returns 3 + SumArray(3) SumArray(3) returns 0 (base case)

2. Step 2: Calculate total sum

   Sum = 1 + 2 + 3 + 0 = 6

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Sum of [1,2,3] = 6 [OK]

Hint: Add current element + recursive sum of rest [OK]

Common Mistakes:

• Forgetting base case leads to infinite recursion
• Returning wrong index or value
• Confusing index with length

4. Identify the error in this recursive function that reverses a string:

static string Reverse(string s) {
  if (s.Length == 0) return s;
  return Reverse(s.Substring(1)) + s[0];
}

// Usage: Console.WriteLine(Reverse(null));

medium

A. It causes a NullReferenceException when input is null

B. It never reaches the base case

C. It returns the original string without reversing

D. It causes infinite recursion

Solution

1. Step 1: Analyze input null handling

   The function calls s.Length but if s is null, this causes NullReferenceException.

2. Step 2: Check base case and usage

   Base case is correct for empty string but does not handle null input, causing runtime error.

3. Final Answer:

   It causes a NullReferenceException when input is null -> Option A

4. Quick Check:

   Null input causes exception [OK]

Hint: Always check for null before accessing string properties [OK]

Common Mistakes:

• Not checking for null input
• Assuming empty string and null are same
• Ignoring exceptions from null dereference

5. Given a string, write a recursive function to check if it is a palindrome (reads same forward and backward). Which of these approaches is correct?

hard

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

B. Check if first and last characters are equal, then recurse on substring excluding them

C. Count characters recursively and check if count is even

D. Reverse the string using recursion and compare with original

Solution

1. Step 1: Understand palindrome check logic

   Palindrome means first and last characters match, and inner substring is also palindrome.

2. Step 2: Apply recursion

   Recursively check first and last chars, then call function on substring excluding them until base case (empty or single char).

3. Final Answer:

   Check if first and last characters are equal, then recurse on substring excluding them -> Option B

4. Quick Check:

   Palindrome check = compare ends + recurse [OK]

Hint: Compare ends, then recurse inside substring [OK]

Common Mistakes:

• Reversing string is less efficient
• Counting characters doesn't prove palindrome
• Sorting changes string order