Recursion vs Iteration When Each Wins in DSA C - Complexity Comparison

Time Complexity: Recursion vs Iteration When Each Wins

O(n)

Understanding Time Complexity

We want to understand how recursion and iteration compare in time cost for solving problems.

Which method grows faster in work as input size increases?

Scenario Under Consideration

Analyze the time complexity of these two ways to sum numbers from 1 to n.

// Recursive sum
int sum_recursive(int n) {
    if (n == 0) return 0;
    return n + sum_recursive(n - 1);
}

// Iterative sum
int sum_iterative(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}
    

Both calculate the sum from 1 to n but use different approaches.

Identify Repeating Operations

Look at what repeats in each method.

• Primary operation: Adding numbers from 1 to n.
• How many times: Both do this n times; recursion calls itself n times, iteration loops n times.

How Execution Grows With Input

As n grows, both methods do more additions.

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

Pattern observation: The work grows directly with n; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Recursion is always slower and less efficient than iteration."

[OK] Correct: Both can have the same time complexity; recursion can be clearer or better for some problems, and iteration can sometimes use less memory.

Interview Connect

Understanding when recursion or iteration is better helps you choose the right tool and explain your reasoning clearly in interviews.

Self-Check

"What if the recursive function used memoization to save results? How would that affect time complexity?"