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?"