Recursion on Arrays and Strings in DSA Typescript

Mental Model

Recursion solves a problem by breaking it into smaller parts of the same kind until it reaches the simplest case.

Analogy: Imagine peeling an onion layer by layer until you reach the center; each peel is like a smaller problem solved step by step.

array: [a, b, c, d, e]
indexes:  0  1  2  3  4

string: "hello"
indexes:  0  1  2  3  4

Recursion calls:
call 1 -> call 2 -> call 3 -> ... -> base case

Dry Run Walkthrough

Input: array: [1, 2, 3, 4], find sum using recursion

Goal: Calculate the sum of all elements in the array by breaking the problem into smaller parts

Step 1: call sum on [1, 2, 3, 4]

[1, 2, 3, 4]

Why: Start with the full array to sum all elements

Step 2: sum = first element (1) + sum of rest [2, 3, 4]

[2, 3, 4]

Why: Break problem into sum of first element plus sum of remaining elements

Step 3: sum = 2 + sum of [3, 4]

[3, 4]

Why: Keep breaking down until only one element remains

Step 4: sum = 3 + sum of [4]

[4]

Why: Approach base case where only one element is left

Step 5: sum = 4 (base case reached)

[]

Why: Base case: sum of single element array is the element itself

Step 6: return 4 to previous call, sum = 3 + 4 = 7

[3, 4]

Why: Combine results going back up the call stack

Step 7: return 7 to previous call, sum = 2 + 7 = 9

[2, 3, 4]

Why: Add partial sums as recursion unwinds

Step 8: return 9 to first call, sum = 1 + 9 = 10

[1, 2, 3, 4]

Why: Final sum is total of all elements

Result:

Final sum = 10

Annotated Code

DSA Typescript

class Recursion {
  static sumArray(arr: number[], index = 0): number {
    if (index === arr.length) {
      return 0; // base case: no elements left
    }
    // add current element to sum of rest
    return arr[index] + Recursion.sumArray(arr, index + 1);
  }

  static reverseString(str: string, index = 0): string {
    if (index === str.length) {
      return ""; // base case: empty string
    }
    // reverse rest of string then add current char
    return Recursion.reverseString(str, index + 1) + str[index];
  }
}

// Driver code
const arr = [1, 2, 3, 4];
const sum = Recursion.sumArray(arr);
console.log("Sum of array:", sum);

const s = "hello";
const reversed = Recursion.reverseString(s);
console.log("Reversed string:", reversed);

if (index === arr.length) { return 0; }

base case: stop when index reaches array length

return arr[index] + Recursion.sumArray(arr, index + 1);

add current element and recurse on next index

if (index === str.length) { return ""; }

base case: stop when index reaches string length

return Recursion.reverseString(str, index + 1) + str[index];

recurse on rest of string then add current character

Output

Sum of array: 10

Reversed string: olleh

Complexity Analysis

Time: O(n) because each element or character is processed once in the recursion

Space: O(n) due to recursion call stack growing with input size n

vs Alternative: Iterative approach uses loops and constant space, recursion is simpler to write but uses extra stack space

Edge Cases

empty array or empty string

returns 0 for sum or empty string for reverse immediately

DSA Typescript

if (index === arr.length) { return 0; }

single element array or single character string

returns the element itself or the character itself

DSA Typescript

base case handles when index reaches length

When to Use This Pattern

When a problem asks to process arrays or strings by breaking them down step by step, recursion is a natural fit because it handles smaller parts easily.

Common Mistakes

Mistake: Forgetting the base case causing infinite recursion
Fix: Always include a base case that stops recursion when input is fully processed

Mistake: Not moving the index forward causing repeated calls on same element
Fix: Increment the index parameter in each recursive call to progress through input

Summary

Recursion breaks arrays or strings into smaller parts and solves each part until done.

Use recursion when you want to solve problems by handling one element and the rest separately.

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