Why Recursion on Arrays and Strings in DSA Typescript?

The Big Idea

Discover how a simple trick can turn a big problem into tiny, easy steps!

The Scenario

Imagine you have a long list of names or a long word, and you want to find if a certain name or letter is inside it. Doing this by checking each item one by one can take a lot of time and effort, especially if the list or word is very long.

The Problem

Checking each item manually means you have to remember where you stopped, and it's easy to make mistakes like skipping items or checking the same item twice. It also takes a lot of steps and can be confusing when the list or word is very long.

The Solution

Recursion helps by breaking the problem into smaller, similar problems. Instead of checking the whole list at once, it checks one item and then asks itself to check the rest. This way, the problem becomes simpler and easier to manage, like solving a puzzle piece by piece.

Before vs After

✗ Before

function findItem(list: string[], target: string): boolean {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return true;
  }
  return false;
}

✓ After

function findItemRecursive(list: string[], target: string, index = 0): boolean {
  if (index === list.length) return false;
  if (list[index] === target) return true;
  return findItemRecursive(list, target, index + 1);
}

What It Enables

Recursion on arrays and strings lets you solve complex problems by breaking them down into simple, repeatable steps that are easy to understand and manage.

Real Life Example

Think of searching for a word in a book by checking one page at a time, and if not found, moving to the next page automatically until the word is found or the book ends.

Key Takeaways

Manual checking is slow and error-prone for long lists or strings.

Recursion breaks the problem into smaller, easier parts.

This approach makes complex tasks simpler and more reliable.

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