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.

Practice

1. What does a recursive function on an array typically do?

easy

A. It only works on strings, not arrays.

B. It loops through the array without calling itself.

C. It creates a new array without using recursion.

D. It calls itself with a smaller part of the array until a base case is reached.

Solution

1. Step 1: Understand recursion on arrays

   Recursive functions on arrays call themselves with smaller parts of the array to solve the problem step-by-step.

2. Step 2: Identify the base case

   The recursion stops when the array is empty or has one element, which is the base case.

3. Final Answer:

   It calls itself with a smaller part of the array until a base case is reached. -> Option D

4. Quick Check:

   Recursion = smaller parts + base case [OK]

Hint: Recursion breaks problem into smaller parts until simple case [OK]

Common Mistakes:

• Thinking recursion loops without calling itself
• Confusing recursion with iteration
• Believing recursion only works on strings

2. Which of the following is the correct TypeScript syntax to define a recursive function that sums elements of a number array?

easy

A. function sum(arr: number[]): number { return arr[0] + sum(arr.slice(1)); }

B. function sum(arr: number[]): number { if(arr.length === 0) return 1; return arr[0] + sum(arr.slice(1)); }

C. function sum(arr: number[]): number { if(arr.length === 0) return 0; return arr[0] + sum(arr.slice(1)); }

D. function sum(arr: number[]): number { if(arr.length === 0) return 0; return sum(arr.slice(1)); }

Solution

1. Step 1: Check base case correctness

   The base case should return 0 when array is empty to stop recursion correctly.

2. Step 2: Check recursive call and addition

   The function adds the first element to the sum of the rest of the array recursively.

3. Final Answer:

   function sum(arr: number[]): number { if(arr.length === 0) return 0; return arr[0] + sum(arr.slice(1)); } -> Option C

4. Quick Check:

   Base case returns 0 + recursive sum [OK]

Hint: Base case returns 0; recursive call adds first element [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Returning wrong base case value like 1
• Not adding the first element before recursive call

3. What is the output of this TypeScript code?

function reverseString(s: string): string {
  if (s === "") return "";
  return reverseString(s.slice(1)) + s[0];
}
console.log(reverseString("abc"));

medium

A. "cba"

B. "abc"

C. "bac"

D. Runtime error

Solution

1. Step 1: Trace recursive calls

   reverseString("abc") calls reverseString("bc") + "a"; reverseString("bc") calls reverseString("c") + "b"; reverseString("c") calls reverseString("") + "c".

2. Step 2: Build return values from base case

   reverseString("") returns ""; so reverseString("c") returns "" + "c" = "c"; reverseString("bc") returns "c" + "b" = "cb"; reverseString("abc") returns "cb" + "a" = "cba".

3. Final Answer:

   "cba" -> Option A

4. Quick Check:

   Reverse "abc" = "cba" [OK]

Hint: Recursion reverses string by slicing first char off [OK]

Common Mistakes:

• Confusing order of concatenation
• Forgetting base case returns empty string
• Expecting original string as output

4. Identify the error in this recursive function that counts occurrences of a number in an array:

function countOccurrences(arr: number[], target: number): number {
  if (arr.length === 0) return 0;
  if (arr[0] === target) return 1 + countOccurrences(arr.slice(1), target);
}

medium

A. Missing else case to handle when arr[0] !== target

B. Base case should return 1 instead of 0

C. Function should not use recursion

D. arr.slice(1) is incorrect syntax

Solution

1. Step 1: Check base case and recursive calls

   Base case returns 0 correctly when array is empty. When arr[0] equals target, function returns 1 plus recursive call.

2. Step 2: Identify missing return for else case

   If arr[0] is not target, function does not return anything, causing undefined result and error.

3. Final Answer:

   Missing else case to handle when arr[0] !== target -> Option A

4. Quick Check:

   All paths must return a value [OK]

Hint: Ensure all if branches return a value in recursion [OK]

Common Mistakes:

• Forgetting else return causes undefined
• Changing base case incorrectly
• Thinking recursion is not needed

5. Given a nested array of numbers like [1, [2, [3, 4], 5], 6], which recursive approach correctly flattens it into [1, 2, 3, 4, 5, 6]?

hard

A. Return the array as is without changes.

B. Check if element is array; if yes, recursively flatten it and concatenate; else add element to result.

C. Use a loop to add elements without recursion.

D. Only flatten one level of nested arrays without recursion.

Solution

1. Step 1: Understand nested array flattening

   Flattening requires checking each element; if it is an array, recursively flatten it to handle any depth.

2. Step 2: Build flattened array by concatenation

   For non-array elements, add directly; for arrays, concatenate their flattened results to build final flat array.

3. Final Answer:

   Check if element is array; if yes, recursively flatten it and concatenate; else add element to result. -> Option B

4. Quick Check:

   Recursion handles any depth flattening [OK]

Hint: Recursively flatten nested arrays by checking element type [OK]

Common Mistakes:

• Flattening only one level deep
• Not checking if element is array
• Using loops without recursion for nested arrays