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 a base case in recursion?

A base case is the simplest situation in a recursive function that can be answered directly without further recursion, stopping the recursive calls.

intermediate

How does recursion help in reversing a string?

Recursion reverses a string by taking the first character, calling itself on the rest of the string, and then adding the first character at the end of the reversed substring.

intermediate

Explain how recursion can be used to find the sum of elements in an array.

Recursion sums array elements by adding the first element to the sum of the rest of the array, which is found by calling the same function on the smaller array until the base case (empty array) is reached.

beginner

What happens if a recursive function does not have a proper base case?

Without a proper base case, the recursive function will keep calling itself forever, causing a stack overflow error and crashing the program.

What is the first step in a recursive function processing an array?

A Process the first element and call recursion on the rest

B Process the last element only

C Stop immediately without processing

D Process all elements at once

In recursion on arrays, we usually process the first element and then call the function recursively on the remaining elements.

What is the base case when recursively reversing a string?

A When the string has two characters

B When the string is empty or has one character

C When the string is longer than 5 characters

D When the string contains only vowels

The base case for reversing a string recursively is when the string is empty or has one character, as it is already reversed.

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

A Array length is greater than zero

B Array length is one

C Array length is negative

D Array length is zero

Base cases are for smallest or simplest inputs, so array length greater than zero is not a base case.

What will happen if a recursive function lacks a base case?

A It will return immediately

B It will skip recursion

C It will run forever until a crash

D It will optimize itself

Without a base case, recursion never stops and causes a stack overflow error.

How does recursion simplify problems on strings and arrays?

A By sorting the data first

B By using loops instead

C By ignoring parts of the data

D By breaking the problem into smaller similar problems

Recursion works by dividing a problem into smaller versions of itself, making it easier to solve step by step.

Describe how you would use recursion to find the maximum element in an array.

Think about comparing one element at a time and reducing the problem size.

Explain the role of the base case and recursive case in a function that reverses a string recursively.

Focus on when recursion stops and how the string is rebuilt.

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