Recursion vs Iteration When Each Wins in DSA Typescript - Complexity Comparison

Time Complexity: Recursion vs Iteration When Each Wins

O(n)

Understanding Time Complexity

We want to understand how recursion and iteration perform differently when solving problems.

Which method is faster or better depends on the problem and input size.

Scenario Under Consideration

Analyze the time complexity of these two ways to compute factorial.

function factorialRecursive(n: number): number {
  if (n <= 1) return 1;
  return n * factorialRecursive(n - 1);
}

function factorialIterative(n: number): number {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}
    

Both calculate factorial but one uses recursion, the other uses a loop.

Identify Repeating Operations

Both methods repeat the multiplication operation.

• Primary operation: Multiplying numbers from 1 to n.
• How many times: Exactly n-1 times in both recursion and iteration.

How Execution Grows With Input

As n grows, the number of multiplications grows linearly.

Input Size (n)	Approx. Operations
10	9 multiplications
100	99 multiplications
1000	999 multiplications

Pattern observation: Operations increase directly with n, doubling n doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as input size grows.

Common Mistake

[X] Wrong: "Recursion is always slower and worse than iteration."

[OK] Correct: Recursion can be just as fast as iteration for many problems, and sometimes clearer or easier to write. The difference is often in memory use and overhead, not just speed.

Interview Connect

Understanding when recursion or iteration fits best shows you can choose the right tool for the problem, a skill interviewers appreciate.

Self-Check

"What if the recursive function used memoization? How would that affect time complexity?"