Recursion Base Case and Recursive Case in DSA Typescript - Time & Space Complexity

Time Complexity: Recursion Base Case and Recursive Case

O(n)

Understanding Time Complexity

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

We want to find out how the number of calls grows as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function factorial(n: number): number {
  if (n === 0) {
    return 1; // base case
  }
  return n * factorial(n - 1); // recursive case
}

This code calculates the factorial of a number using recursion with a base case and a recursive case.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The function calls itself once each time with a smaller number.
• How many times: It repeats until the input reaches zero, so about n times.

How Execution Grows With Input

Each time the function calls itself, it does one multiplication and one smaller call.

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

Pattern observation: The number of operations grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the input number gets bigger.

Common Mistake

[X] Wrong: "Recursion always makes the program slow and complex."

[OK] Correct: Simple recursion like this runs in linear time and is easy to understand when base cases stop the calls.

Interview Connect

Understanding how base and recursive cases affect time helps you explain your code clearly and shows you know how recursion works efficiently.

Self-Check

"What if the recursive case called the function twice instead of once? How would the time complexity change?"