Recursion on Arrays and Strings in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is recursion in the context of arrays and strings?

Recursion is a method where a function calls itself to solve smaller parts of a problem, like processing one element of an array or one character of a string at a time until a base case is reached.

beginner

What is the base case in a recursive function working on an array?

The base case is the condition that stops the recursion, often when the array index reaches the end or when the size of the array to process is zero.

intermediate

How does recursion help in reversing a string?

Recursion can reverse a string by swapping the first and last characters and then recursively reversing the substring between them until the base case of a single character or empty string is reached.

beginner

Explain the role of the recursive call in processing arrays.

The recursive call processes a smaller part of the array, usually by moving the index forward or reducing the size, allowing the function to handle one element at a time until the base case.

beginner

Why is it important to have a base case in recursion on strings or arrays?

Without a base case, the recursive function would call itself infinitely, causing a stack overflow. The base case ensures the recursion stops after processing all elements or characters.

What does the base case in a recursive function on an array usually represent?

A When the array is empty or index is out of bounds

B When the array is fully processed

C When the array size doubles

D When the array elements are sorted

The base case typically occurs when the array is empty or the index goes beyond the last element, stopping further recursive calls.

In recursion on strings, what is a common way to reduce the problem size?

A By removing the first or last character

B By adding characters to the string

C By sorting the string

D By converting the string to uppercase

Recursion on strings often reduces the problem by removing the first or last character and processing the smaller substring.

Which of these is NOT a valid base case for recursion on arrays?

A Index equals array length

B Array size is zero

C Index is negative

D Array elements are all equal

The equality of array elements is not a base case; base cases relate to stopping conditions like index bounds or size zero.

What happens if a recursive function on a string has no base case?

A It reverses the string automatically

B It returns the original string

C It runs infinitely causing a crash

D It sorts the string

Without a base case, recursion never stops, leading to infinite calls and eventually a crash.

How can recursion be used to find the sum of elements in an array?

A By removing duplicates recursively

B By adding the first element to the sum of the rest recursively

C By sorting the array recursively

D By multiplying all elements recursively

Recursion sums the first element and then calls itself on the rest of the array until the base case.

Describe how you would write a recursive function to reverse a string.

Think about how to reduce the string size and how to combine results after recursion.

Explain the importance of the base case in recursion on arrays and what could happen if it is missing.

Consider what controls the end of recursive calls.

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