Recursion on Arrays and Strings in DSA Javascript - Execution Trace

Concept Flow - Recursion on Arrays and Strings

Start with full array/string

↓

Check base case: empty or single element?

Yes→Return base result

No↓

Process first element

↓

Call recursion on rest of array/string

↓

Combine first element with recursive result

↓

Return combined result

Recursion breaks the array or string into smaller parts, processes one element, then calls itself on the rest until it reaches the base case.

Execution Sample

DSA Javascript

function sumArray(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumArray(arr.slice(1));
}

console.log(sumArray([1,2,3]));

This code sums all numbers in an array by adding the first element to the sum of the rest recursively.

Execution Table

Step	Operation	Array State	Recursive Call Argument	Return Value	Visual State
1	Call sumArray([1,2,3])	[1,2,3]	[2,3]	?	sumArray([1,2,3]) waiting for sumArray([2,3])
2	Call sumArray([2,3])	[2,3]	[3]	?	sumArray([2,3]) waiting for sumArray([3])
3	Call sumArray([3])	[3]	[]	?	sumArray([3]) waiting for sumArray([])
4	Call sumArray([])	[]	N/A	0	Base case reached, returns 0
5	Return from sumArray([])	[]	N/A	0	sumArray([3]) computes 3 + 0 = 3
6	Return from sumArray([3])	[3]	[]	3	sumArray([2,3]) computes 2 + 3 = 5
7	Return from sumArray([2,3])	[2,3]	[3]	5	sumArray([1,2,3]) computes 1 + 5 = 6
8	Return from sumArray([1,2,3])	[1,2,3]	[2,3]	6	Final result 6 returned

💡 Recursion stops when array is empty (base case), returning 0.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
arr	[1,2,3]	[1,2,3]	[2,3]	[3]	[]	[]	[3]	[2,3]	[1,2,3]
Return Value	N/A	?	?	?	0	3	5	6	6

Key Moments - 3 Insights

Why does the recursion stop when the array is empty?

Because the base case checks if the array length is zero (step 4), returning 0 to stop further calls, as shown in the execution_table row 4.

How does the function combine results from recursive calls?

Each call adds the first element of its array to the return value of the recursive call on the rest of the array, as seen in steps 5 to 7 in the execution_table.

Why do we use arr.slice(1) in the recursive call?

Because slice(1) creates a new array without the first element, allowing recursion to process the smaller problem, shown in the Recursive Call Argument column.

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value at step 6?

A 0

B 3

C 5

D 6

💡 Hint

Check the Return Value column at step 6 in the execution_table.

At which step does the base case trigger and stop recursion?

A Step 5

B Step 3

C Step 4

D Step 7

💡 Hint

Look for the step where the array is empty and return value is 0 in the execution_table.

If the input array was [4,5], what would be the return value at the final step?

A 9

B 5

C 4

D 0

💡 Hint

Sum of 4 and 5 is 9; relate to how sumArray adds elements recursively.

Concept Snapshot

Recursion on Arrays and Strings:
- Base case: empty array/string returns a simple result.
- Recursive case: process first element + recurse on rest.
- Use slice(1) to reduce problem size.
- Combines results on return.
- Stops when base case reached.

Full Transcript

Recursion on arrays and strings works by breaking the problem into smaller parts. The function checks if the array or string is empty, which is the base case to stop recursion. If not empty, it processes the first element and calls itself on the rest. Each recursive call waits for the smaller problem to solve, then combines the result with the first element. This continues until the base case returns a simple value, and all calls return combined results back up. The example sums an array by adding the first number to the sum of the rest recursively.

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