Recursion on Arrays and Strings in DSA Typescript - 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 a base case is reached.

Execution Sample

DSA Typescript

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

This function 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]	pending	sumArray([1,2,3]) waiting for sumArray([2,3])
2	Call sumArray([2,3])	[2,3]	[3]	pending	sumArray([2,3]) waiting for sumArray([3])
3	Call sumArray([3])	[3]	[]	pending	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	pending	pending	pending	0	3	5	6	6

Key Moments - 3 Insights

Why does the function call itself with arr.slice(1) instead of arr?

Because each recursive call must work on a smaller part of the array to reach the base case. The execution_table rows 1-4 show how the array gets smaller each time.

What is the base case and why is it important?

The base case is when the array is empty (arr.length === 0), returning 0 immediately. This stops infinite recursion. See step 4 in the execution_table where the base case returns 0.

How does the function combine results from recursive calls?

After the recursive call returns, the function adds the first element to the returned sum. This is shown in steps 5-7 where return values are combined step-by-step.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the return value and why?

A 0, because the array is empty (base case)

B 3, because it's the last element

C undefined, because no return statement

D 1, because it's the first element

💡 Hint

Check the 'Return Value' and 'Operation' columns at Step 4 where the base case is reached.

At which step does the function start combining the first element with the recursive result?

A Step 2

B Step 5

C Step 1

D Step 8

💡 Hint

Look at the 'Return Value' and 'Visual State' columns where the function returns from sumArray([]) and adds 3 + 0.

If the input array was empty from the start, how many steps would the execution_table have?

A 3 steps

B 2 steps

C 1 step

D No steps

💡 Hint

Refer to the base case in the execution_table where the array is empty and the function returns immediately.

Concept Snapshot

Recursion on Arrays and Strings:
- Base case: empty or single element array/string
- Process first element
- Recursively call on rest (slice(1))
- Combine first element with recursive result
- Stops when base case reached
- Useful for sums, searches, reversals

Full Transcript

Recursion on arrays and strings works by breaking the problem into smaller parts. We check if the array or string is empty or has one element, which is the base case. If yes, we return a simple result. Otherwise, we process the first element and call the function again on the rest of the array or string. This continues until the base case is reached. Then, results are combined as the recursive calls return. For example, summing an array adds the first element to the sum of the rest recursively. The execution table shows each call and return, with the array shrinking each time until empty. This method helps solve problems by dividing them into smaller, easier steps.