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.

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