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

Time Complexity: Recursion Base Case and Recursive Case

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 changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int factorial(int n) {
    if (n == 0) {
        return 1;  // base case
    } else {
        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 per call, reducing n by 1 each time.
• How many times: It repeats until n reaches 0, so approximately n times.

How Execution Grows With Input

Each call does a small amount of work and then calls itself with a smaller number.

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

Pattern observation: The number of calls grows directly with n, so doubling n doubles the calls.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Recursion always means exponential time because it calls itself multiple times."

[OK] Correct: This example calls itself only once per call, so it grows linearly, not exponentially.

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