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

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

O(n)

Understanding Time Complexity

We want to understand why recursion is useful and how its time cost grows compared to loops.

What question are we trying to answer? How does recursion's repeated calls affect execution time?

Scenario Under Consideration

Analyze the time complexity of the following recursive function.

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
    

This code calculates the factorial of a number using recursion by calling itself with smaller values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

Each call waits for the next call to finish, so the number of calls grows directly with n.

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

Pattern observation: The execution grows linearly as input size increases.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Recursion always makes code slower than loops because it repeats too much."

[OK] Correct: Recursion can express problems loops cannot easily handle, like tree traversals, and its time depends on the problem structure, not just repetition.

Interview Connect

Understanding recursion's time cost helps you explain why and when to use it, showing clear thinking about problem solving in interviews.

Self-Check

"What if we changed the recursion to a loop with a stack? How would the time complexity change?"