Recursion on Arrays and Strings in DSA Typescript - Time & Space Complexity

Time Complexity: Recursion on Arrays and Strings

O(n)

Understanding Time Complexity

When we use recursion on arrays or strings, we want to know how the time to finish grows as the input gets bigger.

We ask: How many steps does the function take as the array or string length increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This function adds all numbers in an array by calling itself with the next index until it reaches the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One recursive call per array element to add the value.
• How many times: Exactly once for each element in the array (n times).

How Execution Grows With Input

Each element causes one function call, so operations grow directly with array size.

Input Size (n)	Approx. Operations
10	10 calls
100	100 calls
1000	1000 calls

Pattern observation: The number of steps grows in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Recursion always makes code slower and more complex than loops."

[OK] Correct: Recursion here simply replaces a loop and does the same number of steps, so time complexity stays the same.

Interview Connect

Understanding recursion time helps you explain your solution clearly and shows you know how your code scales with input size.

Self-Check

"What if the function called itself twice per step (like in some tree problems)? How would the time complexity change?"

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