Recursion on Arrays and Strings in DSA Typescript - Build from Scratch

Sum of Array Elements Using Recursion

📖 Scenario: Imagine you have a list of daily expenses and you want to find out the total amount spent. Instead of adding them one by one using a loop, you will use a simple method called recursion to add all the numbers.

🎯 Goal: Build a TypeScript program that uses recursion to calculate the sum of all numbers in an array.

📋 What You'll Learn

Create an array called expenses with exact numbers: 100, 200, 300, 400, 500

Create a variable called length that stores the length of the expenses array

Write a recursive function called sumArray that takes the array and its length as parameters and returns the sum of the elements

Print the result of calling sumArray(expenses, length)

💡 Why This Matters

🌍 Real World

Recursion helps solve problems where a task can be broken down into smaller similar tasks, like calculating totals, searching, or sorting.

💼 Career

Understanding recursion is important for coding interviews and solving complex problems efficiently in software development.

1

Create the expenses array

Create an array called expenses with these exact numbers: 100, 200, 300, 400, 500

DSA Typescript

# Your code here

Hint

Use square brackets [] to create the array and separate numbers with commas.

2

Create the length variable

Create a variable called length that stores the length of the expenses array

DSA Typescript

const expenses: number[] = [100, 200, 300, 400, 500];
# Your code here

Hint

Use the length property of the array to get its size.

3

Write the recursive sumArray function

Write a recursive function called sumArray that takes two parameters: arr (an array of numbers) and n (a number). The function should return the sum of the first n elements of arr. Use the base case when n is 0 to return 0, otherwise return the last element plus the sum of the rest.

DSA Typescript

const expenses: number[] = [100, 200, 300, 400, 500];
const length: number = expenses.length;

# Your code here

Hint

Think of the function calling itself with one less element until it reaches zero.

4

Print the sum of the expenses array

Print the result of calling sumArray(expenses, length) using console.log

DSA Typescript

const expenses: number[] = [100, 200, 300, 400, 500];
const length: number = expenses.length;

function sumArray(arr: number[], n: number): number {
    if (n === 0) {
        return 0;
    } else {
        return arr[n - 1] + sumArray(arr, n - 1);
    }
}

# Your code here

Hint

Use console.log to show the final sum on the screen.

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