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 elements of an array or characters of a string one by one 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 segment to process is zero.

intermediate

How does recursion help in reversing a string?

Recursion reverses a string by swapping characters from the start and end, then calling itself on the smaller substring inside, until the base case of one or zero characters is reached.

beginner

Explain how to find the sum of elements in an array using recursion.

To find the sum recursively, add the first element to the sum of the rest of the array found by a recursive call, stopping when the array is empty (base case).

beginner

What happens if a recursive function on arrays or strings does not have a proper base case?

Without a proper base case, the recursion will continue indefinitely, causing a stack overflow error and crashing the program.

What is the base case when recursively printing all elements of an array?

A When the index reaches the array length

B When the array is empty

C When the first element is zero

D When the last element is reached

The base case is when the index reaches the array length, meaning no more elements to print.

Which of these is a correct recursive step to reverse a string?

A Reverse the string without changing characters

B Swap first and second characters only

C Swap characters randomly

D Swap first and last characters, then reverse the substring inside

The recursive step swaps the first and last characters, then calls itself on the substring inside.

What does a recursive function typically do after processing one element of an array?

A Processes the entire array again

B Returns immediately

C Calls itself with the next element

D Stops execution

After processing one element, the function calls itself with the next element to continue recursion.

Why is a base case important in recursion?

A To stop the recursion and avoid infinite calls

B To start the recursion

C To increase the recursion depth

D To print the array

The base case stops recursion to prevent infinite calls and stack overflow.

How can recursion be used to count the number of characters in a string?

A Count all characters at once

B Count 1 for the first character plus count of the rest recursively

C Use a loop instead

D Count only vowels

Recursion counts 1 for the current character plus the count from the rest of the string.

Describe how recursion works on arrays with an example of summing elements.

Think about stopping condition and how each call handles one element.

Explain the steps to reverse a string using recursion.

Focus on how the string is reduced each time.

Practice

1. What does recursion mean when applied to arrays or strings?

easy

A. A function calls itself to solve smaller parts of the problem

B. A loop runs through all elements once

C. The array or string is sorted automatically

D. The data is copied to a new array or string

Solution

1. Step 1: Understand recursion concept

   Recursion means a function calls itself to break down a problem into smaller parts.

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:

   A function calls itself to solve smaller parts of the problem -> Option A

4. Quick Check:

   Recursion = function calls itself [OK]

Hint: Recursion always involves a function calling itself [OK]

Common Mistakes:

• Confusing recursion with loops
• Thinking recursion sorts data automatically
• Believing recursion copies data

2. Which of the following is the correct base case for a recursive function that processes a string?

easy

A. if (length < 0) return;

B. if (length == 0) return;

C. if (string == NULL) continue;

D. if (length > 0) return;

Solution

1. Step 1: Identify base case role

   The base case stops recursion when no more characters remain, usually length 0.

2. Step 2: Check options for correct base case

   if (length == 0) return; correctly returns when length is 0, stopping recursion safely.

3. Final Answer:

   if (length == 0) return; -> Option B

4. Quick Check:

   Base case stops recursion at empty string [OK]

Hint: Base case usually checks for empty string or zero length [OK]

Common Mistakes:

• Using incorrect base case conditions
• Using continue instead of return
• Checking for negative length which is invalid

3. What is the output of this C code?

void printReverse(char *str) {
  if (*str == '\0') return;
  printReverse(str + 1);
  printf("%c", *str);
}

int main() {
  char s[] = "abc";
  printReverse(s);
  return 0;
}

medium

A. cba

B. abc

C. Syntax error

D. No output

Solution

1. Step 1: Understand recursion flow

   The function calls itself moving forward in the string until it hits '\0' (end).

2. Step 2: Print characters on return

   After reaching end, it prints characters backward as recursion unwinds: 'c', 'b', 'a'.

3. Final Answer:

   cba -> Option A

4. Quick Check:

   Recursion prints string in reverse [OK]

Hint: Recursion with print after call reverses output [OK]

Common Mistakes:

• Expecting normal order output
• Confusing base case with print order
• Thinking code has syntax errors

4. Find the error in this recursive function that counts characters in a string:

int countChars(char *str) {
  if (*str == '\0')
    return 0;
  return 1 + countChars(str);
}

medium

A. Missing base case

B. Return type should be void

C. Recursive call does not move forward in string

D. Should use while loop instead

Solution

1. Step 1: Check base case correctness

   Base case correctly returns 0 when string ends.

2. Step 2: Analyze recursive call

   Recursive call uses same pointer 'str' without moving forward, causing infinite recursion.

3. Final Answer:

   Recursive call does not move forward in string -> Option C

4. Quick Check:

   Pointer must advance in recursion [OK]

Hint: Always move pointer forward in recursive calls on strings [OK]

Common Mistakes:

• Forgetting to advance pointer
• Changing return type unnecessarily
• Replacing recursion with loops without reason

5. You want to write a recursive function to check if a string is a palindrome (reads same forward and backward). Which approach is best?

hard

A. Count characters recursively and check if count is even

B. Reverse the string using recursion and compare with original

C. Use recursion to sort the string and compare with original

D. Compare first and last characters, then recurse on substring excluding them

Solution

1. Step 1: Understand palindrome check logic

   Palindrome means first and last characters must match, then check inside substring.

2. Step 2: Apply recursion on substring

   Recursively check smaller substring by removing first and last characters each time.

3. Final Answer:

   Compare first and last characters, then recurse on substring excluding them -> Option D

4. Quick Check:

   Check ends and recurse inside for palindrome [OK]

Hint: Check ends match, then recurse inside substring [OK]

Common Mistakes:

• Reversing string unnecessarily
• Counting characters instead of comparing ends
• Sorting string which changes order