Recursion on Arrays and Strings in DSA C# - Time & Space Complexity

Time Complexity: Recursion on Arrays and Strings

O(n)

Understanding Time Complexity

When using recursion on arrays or strings, we want to know how the number of steps grows as the input gets bigger.

We ask: How many times does the function call itself and how much work does it do each time?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code sums all elements in an array by calling itself for each index until it reaches the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive call to SumArray for each index.
• How many times: Once per element in the array, so n times for array length n.

How Execution Grows With Input

Each element causes one recursive call doing a simple addition.

Input Size (n)	Approx. Operations
10	About 10 additions and 10 calls
100	About 100 additions and 100 calls
1000	About 1000 additions and 1000 calls

Pattern observation: The work grows directly with the size of the array, increasing steadily.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Recursion always makes the code slower and more complex than loops."

[OK] Correct: Recursion here simply replaces a loop and does the same amount of work, so time complexity stays the same.

Interview Connect

Understanding recursion time helps you explain your code clearly and shows you know how your solution scales with input size.

Self-Check

"What if the recursion called itself twice per step (like in a binary tree)? How would the time complexity change?"

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