Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Typescript - Performance Analysis

Time Complexity: Why Recursion Exists and What Loops Cannot Express Cleanly

O(n)

Understanding Time Complexity

We explore why recursion is useful and how it differs from loops in expressing repeated tasks.

We want to understand how the time cost grows when using recursion compared to loops.

Scenario Under Consideration

Analyze the time complexity of this recursive function that calculates factorial.

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

This function calls itself to multiply numbers from n down to 1.

Identify Repeating Operations

Look for repeated actions in the code.

• Primary operation: Recursive call to factorial with n-1.
• How many times: Exactly n times until base case (n=1) is reached.

How Execution Grows With Input

Each call waits for the next call to finish, so the total steps grow with n.

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

Pattern observation: The number of operations grows directly with n, linearly.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows in a straight line as n gets bigger.

Common Mistake

[X] Wrong: "Recursion always takes more time than loops."

[OK] Correct: Both recursion and loops can do the same number of steps; recursion just expresses the steps differently.

Interview Connect

Understanding recursion's time cost helps you explain your choices clearly and shows you know when recursion is a good fit.

Self-Check

"What if the factorial function used a loop instead of recursion? How would the time complexity change?"