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.