Recursion on Arrays and Strings in DSA C#

Mental Model

Recursion breaks a big problem into smaller similar problems until it becomes simple enough to solve directly.

Analogy: Like peeling an onion layer by layer until you reach the core, recursion processes arrays or strings one element at a time until nothing is left.

Array: [1, 2, 3, 4, 5]
String: "hello"
Recursion starts at first element and moves forward ->
[1] -> [2] -> [3] -> [4] -> [5] -> null
h -> e -> l -> l -> o -> null

Dry Run Walkthrough

Input: array: [1, 2, 3], sum all elements using recursion

Goal: Calculate the sum of all elements by breaking the problem into smaller parts

Step 1: Start with first element 1, call recursion on rest [2, 3]

[1, 2, 3] ↑ at index 0

Why: We want to add current element and sum of the rest

Step 2: At index 1, element 2, call recursion on [3]

[1, 2, 3] ↑ at index 1

Why: Keep breaking problem smaller by moving forward

Step 3: At index 2, element 3, call recursion on empty array []

[1, 2, 3] ↑ at index 2

Why: Base case reached when no elements left

Step 4: Base case: empty array returns 0

[] null

Why: Sum of no elements is zero

Step 5: Return 3 + 0 = 3 to previous call

[3] returns 3

Why: Add current element to sum of rest

Step 6: Return 2 + 3 = 5 to previous call

[2, 3] returns 5

Why: Add current element to sum of rest

Step 7: Return 1 + 5 = 6 as final sum

[1, 2, 3] returns 6

Why: Add current element to sum of rest to get total

Result:

Final sum = 6

Annotated Code

DSA C#

using System;

class RecursionArray {
    // Recursive function to sum elements from index to end
    static int SumArray(int[] arr, int index) {
        if (index == arr.Length) {
            return 0; // base case: no elements left
        }
        // add current element to sum of rest
        return arr[index] + SumArray(arr, index + 1);
    }

    static void Main() {
        int[] array = {1, 2, 3};
        int result = SumArray(array, 0);
        Console.WriteLine("Sum of array elements: " + result);
    }
}

if (index == arr.Length) {

check base case when no elements left to add

return 0; // base case: no elements left

return zero as sum of empty part

return arr[index] + SumArray(arr, index + 1);

add current element to sum of remaining elements recursively

Output

Sum of array elements: 6

Complexity Analysis

Time: O(n) because the recursion visits each element once

Space: O(n) due to call stack growing with each recursive call for n elements

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to write and understand for beginners

Edge Cases

empty array

returns 0 immediately without recursion

DSA C#

if (index == arr.Length) {

single element array

returns that element as sum

DSA C#

return arr[index] + SumArray(arr, index + 1);

When to Use This Pattern

When you need to process arrays or strings by breaking them down element by element, recursion is a natural fit because it handles smaller parts easily.

Common Mistakes

Mistake: Forgetting the base case causing infinite recursion
Fix: Always include a base case that stops recursion when no elements remain

Mistake: Not advancing the index leading to repeated calls on same element
Fix: Increment the index in the recursive call to move forward

Summary

Recursion on arrays and strings breaks the problem into smaller parts by processing one element at a time.

Use recursion when you want to solve problems by reducing them step-by-step on arrays or strings.

The key insight is to define a base case and reduce the problem size in each recursive call.

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