Recursion on Arrays and Strings in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Sum of Array Elements

What is the output of this TypeScript code that sums elements of an array recursively?

DSA Typescript

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

const result = recursiveSum([1, 2, 3, 4]);
console.log(result);

A TypeError

B 10

C 0

D 24

💡 Hint

Think about how the function adds each element starting from index 0 until the end.

The function adds each element starting from index 0 recursively until it reaches the end, summing 1+2+3+4 = 10.

❓ Predict Output

intermediate

Output of Recursive String Reverse

What is the output of this TypeScript code that reverses a string recursively?

DSA Typescript

function reverseString(str: string): string {
  if (str === "") return "";
  return reverseString(str.substr(1)) + str.charAt(0);
}

const reversed = reverseString("code");
console.log(reversed);

A "

B code

C edoc

D RangeError

💡 Hint

The function takes the first character and puts it at the end after reversing the rest.

The function reverses the string by recursively calling itself on the substring excluding the first character and appending the first character at the end.

🔧 Debug

advanced

Identify the Error in Recursive Array Search

What error does this TypeScript code produce when searching for a value recursively in an array?

DSA Typescript

function recursiveSearch(arr: number[], target: number, index: number = 0): boolean {
  if (index >= arr.length) return false;
  if (arr[index] === target) return true;
  return recursiveSearch(arr, target, index + 1);
}

console.log(recursiveSearch([5, 3, 7], 7));

A No error, outputs true

B TypeError

C undefined is not a number

D StackOverflowError

💡 Hint

Check the base case condition for index exceeding array length.

The base case was originally 'index > arr.length' which allowed index to equal arr.length causing arr[index] to be undefined and comparing undefined to target causes a TypeError. Changing it to 'index >= arr.length' fixes the error.

❓ Predict Output

advanced

Output of Recursive Flattening of Nested Arrays

What is the output of this TypeScript code that recursively flattens a nested array?

DSA Typescript

function flatten(arr: any[]): any[] {
  if (arr.length === 0) return [];
  const [first, ...rest] = arr;
  if (Array.isArray(first)) {
    return [...flatten(first), ...flatten(rest)];
  } else {
    return [first, ...flatten(rest)];
  }
}

const nested = [1, [2, [3, 4], 5], 6];
console.log(flatten(nested));

A [1, 2, 3, 4, 5, 6]

B [1, [2, [3, 4], 5], 6]

C [[1, 2], 3, 4, 5, 6]

D TypeError

💡 Hint

The function checks if the first element is an array and flattens it recursively.

The function recursively flattens nested arrays by concatenating flattened first element and flattened rest of the array.

🧠 Conceptual

expert

Maximum Call Stack Depth in Recursive Palindrome Check

Consider this recursive TypeScript function that checks if a string is a palindrome. What is the maximum depth of the call stack for a string of length n?

DSA Typescript

function isPalindrome(str: string, left: number = 0, right: number = str.length - 1): boolean {
  if (left >= right) return true;
  if (str[left] !== str[right]) return false;
  return isPalindrome(str, left + 1, right - 1);
}

A n - 1

B n

C Math.ceil(n / 2)

D Math.floor(n / 2)

💡 Hint

Each recursive call moves inward from both ends by one character.

The function calls itself reducing the problem size by two characters each time, so maximum depth is floor of n/2.

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