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]
Indexes:  0  1  2  3  4

String: "hello"
Indexes:  0  1  2  3  4

Recursion starts at index 0 and moves forward ->

Dry Run Walkthrough

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

Goal: Calculate the sum of all elements in the array using recursion

Step 1: Call sum function with index 0

sum([1, 2, 3], index=0) -> needs sum of elements from index 0 to end

Why: Start from the first element to include all elements in sum

Step 2: Call sum function with index 1 inside previous call

sum([1, 2, 3], index=1) -> needs sum of elements from index 1 to end

Why: Move to next element to break problem into smaller part

Step 3: Call sum function with index 2 inside previous call

sum([1, 2, 3], index=2) -> needs sum of elements from index 2 to end

Why: Keep moving forward until last element

Step 4: Call sum function with index 3 (beyond last index) returns 0

sum([1, 2, 3], index=3) -> base case reached, return 0

Why: No elements left to add, stop recursion

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

sum at index 2 is 3

Why: Add current element to sum of rest

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

sum at index 1 is 5

Why: Add current element to sum of rest

Step 7: Return 1 + 5 = 6 to original call

sum at index 0 is 6

Why: Add current element to sum of rest

Result:

Final sum = 6

Annotated Code

DSA C++

#include <iostream>
#include <vector>

// Recursive function to find sum of array elements from index to end
int recursiveSum(const std::vector<int>& arr, int index) {
    if (index == arr.size()) {
        return 0; // base case: no elements left
    }
    // add current element to sum of rest
    return arr[index] + recursiveSum(arr, index + 1);
}

int main() {
    std::vector<int> arr = {1, 2, 3};
    int result = recursiveSum(arr, 0);
    std::cout << "Sum of array elements: " << result << std::endl;
    return 0;
}

if (index == arr.size()) {

base case: stop recursion when index reaches array length

return 0;

return 0 because no elements left to add

return arr[index] + recursiveSum(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 function visits each element once

Space: O(n) due to recursion call stack growing with array size

vs Alternative: Iterative sum uses O(1) space but recursion is easier to understand for beginners

Edge Cases

empty array

returns 0 immediately as base case triggers

DSA C++

if (index == arr.size()) {

array with one element

returns that element as sum

DSA C++

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

When to Use This Pattern

When you need to process arrays or strings by breaking the problem into smaller parts, recursion is a natural fit because it handles one element at a time.

Common Mistakes

Mistake: Forgetting the base case causing infinite recursion
Fix: Add a condition to stop recursion when index reaches array length

Mistake: Not advancing the index in recursive call causing repeated calls on same element
Fix: Increase index by 1 in recursive call to move forward

Summary

Recursion on arrays and strings solves problems by handling one element and calling itself on the rest.

Use recursion when a problem can be divided into smaller similar problems on parts of the array or string.

The key insight is the base case stops recursion and each call processes one element before moving forward.

Practice

1. What does a recursive function on an array typically do to process the array elements?

easy

A. It processes one element and calls itself on the rest of the array

B. It processes all elements at once without calling itself

C. It uses loops instead of calling itself

D. It only processes the last element of the array

Solution

1. Step 1: Understand recursion on arrays

   A recursive function on an array usually handles one element and then calls itself on the remaining elements.

2. Step 2: Compare options

   It processes one element and calls itself on the rest of the array matches this behavior. Options A, C, and D describe non-recursive or incorrect methods.

3. Final Answer:

   It processes one element and calls itself on the rest of the array -> Option A

4. Quick Check:

   Recursion on arrays = process one element + recurse [OK]

Hint: Remember recursion breaks problem into smaller parts [OK]

Common Mistakes:

• Thinking recursion processes all elements at once
• Confusing recursion with loops
• Assuming recursion only processes last element

2. Which of the following is the correct base case for a recursive function that sums elements of an integer array arr of size n?

easy

A. if (n == 0) return 0;

B. if (n == 1) return arr[1];

C. if (arr == NULL) return 0;

D. if (n < 0) return 0;

Solution

1. Step 1: Identify base case for recursion on array size

   The base case should stop recursion when no elements are left, which is when n == 0.

2. Step 2: Check each option

   if (n == 0) return 0; returns 0 when n == 0, which is correct. if (n == 1) return arr[1]; incorrectly accesses arr[1] instead of arr[0]. if (arr == NULL) return 0; checks pointer but not size. if (n < 0) return 0; uses invalid negative size.

3. Final Answer:

   if (n == 0) return 0; -> Option A

4. Quick Check:

   Base case for empty array = return 0 [OK]

Hint: Base case usually when size is zero [OK]

Common Mistakes:

• Using wrong index in base case
• Checking pointer instead of size
• Allowing negative sizes

3. What is the output of the following C++ code?

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

int main() {
  int arr[] = {1, 2, 3, 4};
  int result = sumArray(arr, 4);
  std::cout << result;
  return 0;
}

medium

A. Compilation error

B. 24

C. 0

D. 10

Solution

1. Step 1: Trace recursive calls

   sumArray(arr,4) = arr[3] + sumArray(arr,3) = 4 + sumArray(arr,3) sumArray(arr,3) = arr[2] + sumArray(arr,2) = 3 + sumArray(arr,2) sumArray(arr,2) = arr[1] + sumArray(arr,1) = 2 + sumArray(arr,1) sumArray(arr,1) = arr[0] + sumArray(arr,0) = 1 + 0 = 1

2. Step 2: Calculate total sum

   Total = 4 + 3 + 2 + 1 = 10

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Sum of {1,2,3,4} = 10 [OK]

Hint: Sum recursion adds last element + sum of rest [OK]

Common Mistakes:

• Confusing index n-1 with n
• Forgetting base case returns 0
• Assuming sum is product

4. Find the error in this recursive function that counts occurrences of character c in string s:

int countChar(string s, char c, int index) {
  if (index == s.length()) return 0;
  if (s[index] == c) return 1 + countChar(s, c, index++);
  else return countChar(s, c, index++);
}

medium

A. Missing check for empty string

B. Base case condition is wrong

C. Using post-increment (index++) causes infinite recursion

D. Function should return bool, not int

Solution

1. Step 1: Analyze recursive calls with index++

   Using index++ passes the current index value before increment, so recursive call uses same index repeatedly.

2. Step 2: Identify infinite recursion cause

   Because index does not increase in recursive calls, base case is never reached, causing infinite recursion.

3. Final Answer:

   Using post-increment (index++) causes infinite recursion -> Option C

4. Quick Check:

   Post-increment in recursion argument = infinite loop [OK]

Hint: Use pre-increment (++index) or index+1 in recursion call [OK]

Common Mistakes:

• Using post-increment in recursive call argument
• Ignoring base case correctness
• Confusing return types

5. Given a string s, write a recursive function to check if it is a palindrome (reads same forward and backward). Which approach below correctly implements this?

hard

A. Reverse string using loop and compare with original

B. Check if first and last chars match, then recurse on substring excluding them

C. Count matching characters from start only

D. Use recursion to count characters and compare counts

Solution

1. Step 1: Understand palindrome check recursively

   To check palindrome recursively, compare first and last characters; if they match, recurse on substring excluding them.

2. Step 2: Evaluate options

   Check if first and last chars match, then recurse on substring excluding them matches this logic. Reverse string using loop and compare with original uses loops, not recursion. Options C and D do not correctly check palindrome property.

3. Final Answer:

   Check if first and last chars match, then recurse on substring excluding them -> Option B

4. Quick Check:

   Palindrome recursion = compare ends + recurse inside [OK]

Hint: Compare ends, recurse inside substring [OK]

Common Mistakes:

• Using loops instead of recursion
• Only checking one side of string
• Counting chars instead of comparing