Recursion on Arrays and Strings in DSA Javascript

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: [a, b, c, d, e]
string: "abcde"

Recursion call stack:
call 1 -> process 'a' + call 2
call 2 -> process 'b' + call 3
call 3 -> ... until base case

Dry Run Walkthrough

Input: array: [1, 2, 3], reverse it using recursion

Goal: Reverse the array using recursion by swapping elements from ends moving inward

Step 1: swap first (1) and last (3) elements

[3, 2, 1]

Why: Swap outer elements to start reversing the array

Step 2: recurse on the middle element (2) only

[3, 2, 1]

Why: Middle element is alone, base case reached, no swap needed

Step 3: return from recursion, final reversed array ready

[3, 2, 1]

Why: All swaps done, recursion unwinds

Result:

[3, 2, 1]

Annotated Code

DSA Javascript

class RecursiveArray {
  static reverse(arr, start = 0, end = arr.length - 1) {
    if (start >= end) return; // base case: pointers crossed or equal
    // swap elements at start and end
    [arr[start], arr[end]] = [arr[end], arr[start]];
    // recurse inward
    RecursiveArray.reverse(arr, start + 1, end - 1);
  }
}

// driver code
const arr = [1, 2, 3];
RecursiveArray.reverse(arr);
console.log(arr.join(' -> ') + ' -> null');

if (start >= end) return; // base case: pointers crossed or equal

stop recursion when start meets or passes end

[arr[start], arr[end]] = [arr[end], arr[start]];

swap elements at current start and end positions

RecursiveArray.reverse(arr, start + 1, end - 1);

recurse inward to next pair of elements

Output

3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because each element is swapped once during recursion

Space: O(n) due to recursion call stack depth proportional to half the array size

vs Alternative: Iterative reversal uses O(1) space but recursion is simpler to write and understand for beginners

Edge Cases

empty array []

base case triggers immediately, no swaps, array remains empty

DSA Javascript

if (start >= end) return;

single element array [5]

base case triggers immediately, no swaps, array unchanged

DSA Javascript

if (start >= end) return;

array with duplicates [2, 2, 2]

swaps happen but elements are same, array remains effectively unchanged

DSA Javascript

[arr[start], arr[end]] = [arr[end], arr[start]];

When to Use This Pattern

When you need to process arrays or strings by breaking them down into smaller parts and combining results, recursion is a natural fit because it handles the repeated smaller problems automatically.

Common Mistakes

Mistake: Forgetting the base case causing infinite recursion
Fix: Add a clear base case like 'if (start >= end) return;' to stop recursion

Mistake: Swapping elements incorrectly or swapping after recursive call
Fix: Always swap before the recursive call to ensure correct order

Summary

Recursion on arrays and strings breaks the problem into smaller parts until a simple base case is reached.

Use recursion when you want to process or transform arrays or strings step-by-step from ends or parts inward.

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

Practice

1. What does a recursive function on an array typically do to process the array elements?

easy

A. It uses loops instead of calling itself.

B. It processes one element and calls itself on the rest of the array.

C. It processes all elements at once without calling itself.

D. It only processes the first and last elements.

Solution

1. Step 1: Understand recursion on arrays

   Recursive functions handle one element and then call themselves on the smaller part (rest of the array).

2. Step 2: Identify the typical recursive pattern

   This pattern reduces the problem size by one element each call until the array is empty.

3. Final Answer:

   It processes one element and calls itself on the rest of the array. -> Option B

4. Quick Check:

   Recursion = process one + recurse rest [OK]

Hint: Recursion breaks problem into smaller parts [OK]

Common Mistakes:

• Thinking recursion processes all elements at once
• Confusing recursion with loops
• Ignoring the base case

2. Which of the following is the correct syntax to define a recursive function in JavaScript that takes an array as input?

easy

A. function recurse(arr) { if(arr.length === 0) return; recurse(arr.slice(1)); }

B. function recurse(arr) { while(arr.length > 0) recurse(arr); }

C. function recurse(arr) { for(let i=0; i

D. function recurse(arr) { if(arr.length === 0) return; recurse(arr.pop()); }

Solution

1. Step 1: Check base case and recursive call

   function recurse(arr) { if(arr.length === 0) return; recurse(arr.slice(1)); } correctly checks if array is empty and calls itself with the rest of the array using slice(1).

2. Step 2: Identify incorrect syntax in other options

   The version using while(arr.length > 0) recurse(arr); causes infinite recursion because it passes the same array; the version using for loop calls recurse on individual elements; the version using arr.pop() passes a single element, not an array.

3. Final Answer:

   function recurse(arr) { if(arr.length === 0) return; recurse(arr.slice(1)); } -> Option A

4. Quick Check:

   Base case + recurse smaller array = correct syntax [OK]

Hint: Base case + smaller input slice needed [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Passing wrong argument type in recursive call
• Using loops inside recursion incorrectly

3. What will be the output of the following code?

function sumArray(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumArray(arr.slice(1));
}
console.log(sumArray([1, 2, 3, 4]));

medium

A. 1234

B. Error

C. undefined

D. 10

Solution

1. Step 1: Understand the recursive sum logic

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

2. Step 2: Calculate sum step-by-step

   1 + sumArray([2,3,4]) = 1 + (2 + sumArray([3,4])) = 1 + 2 + 3 + 4 = 10

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Sum of [1,2,3,4] = 10 [OK]

Hint: Sum = first element + sum of rest [OK]

Common Mistakes:

• Concatenating numbers as strings
• Forgetting base case returns 0
• Using arr.pop() which mutates array

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

function reverseStr(str) {
  if (str.length === 1) return str;
  return reverseStr(str.slice(1)) + str[0];
}
console.log(reverseStr('abc'));

medium

A. Base case should check for empty string, not length 1.

B. The recursive call should use str.slice(0, -1) instead of str.slice(1).

C. The function should return str[0] + reverseStr(str.slice(1)) instead.

D. No error, the function works correctly.

Solution

1. Step 1: Analyze base case condition

   Base case checks if string length is 1, but for empty string it should return empty string to avoid errors.

2. Step 2: Understand recursion on empty string

   If input is empty, function should return empty string to stop recursion safely.

3. Final Answer:

   Base case should check for empty string, not length 1. -> Option A

4. Quick Check:

   Base case empty string needed for safe recursion [OK]

Hint: Base case must handle empty string [OK]

Common Mistakes:

• Using wrong base case length
• Confusing slice indexes
• Assuming function works without base case

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

hard

A. Return the original array as is without changes.

B. Use a loop to add elements without recursion.

C. Check if element is array, recursively flatten it, else add element to result.

D. Only flatten one level using slice and concat.

Solution

1. Step 1: Identify recursive flattening logic

   To flatten nested arrays, check each element: if array, recurse; else add to result.

2. Step 2: Understand why other options fail

   Loops alone can't flatten nested arrays fully; one-level flattening misses deeper nesting; returning original array does nothing.

3. Final Answer:

   Check if element is array, recursively flatten it, else add element to result. -> Option C

4. Quick Check:

   Recursive flatten = check array + recurse + add element [OK]

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

Common Mistakes:

• Flattening only one level
• Not checking if element is array
• Ignoring nested deeper arrays