Recursion Concept and Call Stack Visualization in DSA Typescript - Time & Space Complexity

Time Complexity: Recursion Concept and Call Stack Visualization

O(n)

Understanding Time Complexity

When using recursion, it is important to understand how many times the function calls itself.

We want to know how the number of calls grows as the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following recursive function.

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

This function calculates the factorial of a number by calling itself with a smaller number until it reaches 1.

Identify Repeating Operations

Look at what repeats in this code:

• Primary operation: The function calls itself once each time with n reduced by 1.
• How many times: It repeats until n reaches 1, so about n times.

How Execution Grows With Input

Each increase in n adds one more function call.

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

Pattern observation: The number of calls grows directly with n, so it grows in a straight line.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows in direct proportion to the input size.

Common Mistake

[X] Wrong: "Recursion always makes the program slow and complex because it repeats too much."

[OK] Correct: Recursion can be simple and efficient if each call does a small, fixed amount of work and the number of calls grows linearly.

Interview Connect

Understanding recursion and its time cost helps you explain your solutions clearly and shows you can reason about how your code behaves as inputs grow.

Self-Check

"What if the recursive function called itself twice each time? How would the time complexity change?"