Recursion on Arrays and Strings in DSA C

Mental Model

Recursion solves a problem by breaking it into smaller versions of itself until it reaches a simple case.

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]
String: "hello"
Process first element -> rest -> base case
[1, 2, 3, 4, 5] ↑
"hello" ↑

Dry Run Walkthrough

Input: array: [1, 2, 3], print elements recursively from start to end

Goal: Print each element of the array one by one using recursion

Step 1: Print element at index 0 (1), then call recursion for index 1

[1, 2, 3] ↑ at index 1

Why: We print current element and move to next to cover all elements

Step 2: Print element at index 1 (2), then call recursion for index 2

[1, 2, 3] ↑ at index 2

Why: Continue printing next element until end

Step 3: Print element at index 2 (3), then call recursion for index 3

[1, 2, 3] ↑ at index 3 (end)

Why: Reached last element, next call hits base case

Step 4: Index 3 equals array length, stop recursion

[1, 2, 3] null (end)

Why: Base case stops recursion to avoid infinite calls

Result:

Printed elements: 1 2 3

Annotated Code

DSA C

#include <stdio.h>

void printArrayRec(int arr[], int size, int index) {
    if (index == size) {
        return; // base case: stop when index reaches size
    }
    printf("%d ", arr[index]); // print current element
    printArrayRec(arr, size, index + 1); // recursive call for next element
}

int main() {
    int arr[] = {1, 2, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArrayRec(arr, size, 0);
    printf("\n");
    return 0;
}

if (index == size) {

check base case to stop recursion when all elements are processed

printf("%d ", arr[index]);

print current element at index

printArrayRec(arr, size, index + 1);

recursive call to process next element

Output

1 2 3 

Complexity Analysis

Time: O(n) because each element is visited once in the recursion

Space: O(n) due to recursion call stack growing with each element

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to write and understand for problems naturally defined by smaller subproblems

Edge Cases

empty array

function immediately hits base case and prints nothing

DSA C

if (index == size) {

array with one element

prints the single element then stops

DSA C

if (index == size) {

When to Use This Pattern

When you need to process arrays or strings element by element and the problem can be broken down into smaller similar problems, use recursion to simplify the logic.

Common Mistakes

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

Mistake: Not advancing the index in recursive call
Fix: Increase index by 1 in the recursive call to move forward

Summary

Recursion on arrays and strings processes elements by calling itself on smaller parts until done.

Use it when a problem can be naturally divided into smaller subproblems on parts of the array or string.

The key is to define a clear base case and reduce the problem size each call.

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