Skip to content
StudyFame

Recursion vs Iteration in C

Many problems can be solved in two ways: with a loop (iteration) or with a function that calls itself (recursion). Both give the same answer, so which is better?

In this lesson you will compare them with a clear table, solve one problem both ways, and see a real example where recursion is thousands of times slower.

What You Will Learn

  • The difference between recursion and iteration.
  • The same problem solved both ways.
  • Advantages and disadvantages of recursion.
  • Why naive recursive Fibonacci is slow.
  • When to choose each one.

Recursion vs Iteration in C

Exam definition: Iteration repeats a block of statements using a loop until a condition becomes false. Recursion repeats work by having a function call itself until a base case is reached.

Difference between recursion and iteration

PointRecursionIteration
How it repeatsA function calls itselfA loop (for, while, do-while)
Stops whenThe base case is reachedThe loop condition becomes false
MemoryMore: each call uses a stack frameLess: same variables reused
SpeedUsually slower (function call overhead)Usually faster
If it never stopsStack overflow (crash)Infinite loop (hangs)
Code lengthOften shorter and closer to the mathsOften longer
Best forTrees, divide-and-conquer, Tower of HanoiSimple counting and repetition

Memory trick: Climbing stairs. Iteration = you walk up step by step yourself. Recursion = you ask a friend on the next step to finish the climb, who asks another friend... Every friend waiting on the stairs takes space (stack memory).

Syntax: The Same Repetition in Both Styles

/* iteration */                      /* recursion */
int result = 1;                      int f(int n)
for (int i = n; i > 1; i--)          {
    result *= i;                         if (n <= 1) return 1;
                                         return n * f(n - 1);
                                     }

Example 1: Factorial Using a Loop and Using Recursion

#include <stdio.h>

long long fact_loop(int n)
{
    long long result = 1;
    for (int i = 2; i <= n; i++)
        result *= i;
    return result;
}

long long fact_rec(int n)
{
    if (n <= 1)                  /* base case */
        return 1;
    return n * fact_rec(n - 1);  /* recursive case */
}

int main(void)
{
    printf("Iteration: 10! = %lld\n", fact_loop(10));
    printf("Recursion: 10! = %lld\n", fact_rec(10));
    return 0;
}

Output

Iteration: 10! = 3628800
Recursion: 10! = 3628800

Code Explanation

  1. fact_loop multiplies 2 × 3 × ... × 10 in one loop, using one variable.
  2. fact_rec follows the maths definition n! = n × (n − 1)!, with 1! = 1 as the base case.
  3. Both give 3,628,800. The recursive version makes 10 function calls (10 stack frames); the loop version makes none.

How Recursion Can Become Very Slow

  • Fibonacci: fib(n) = fib(n − 1) + fib(n − 2). Each call makes two more calls.
  • So fib(5) calls fib(4) and fib(3), and fib(4) again calls fib(3). The same values are calculated many times.
  • The number of calls grows almost doubling with each n, which is called exponential growth.
  • A loop calculates each Fibonacci number only once.

Example 2: Counting the Calls in Recursive Fibonacci

#include <stdio.h>

long calls = 0;

int fib_rec(int n)
{
    calls++;
    if (n <= 1)
        return n;
    return fib_rec(n - 1) + fib_rec(n - 2);
}

int fib_loop(int n)
{
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++)
    {
        int next = a + b;
        a = b;
        b = next;
    }
    return n == 0 ? 0 : b;
}

int main(void)
{
    printf("Loop     : fib(20) = %d (19 loop steps)\n", fib_loop(20));

    int r = fib_rec(20);     /* call first: argument order in printf is not fixed */
    printf("Recursion: fib(20) = %d (%ld function calls)\n", r, calls);
    return 0;
}

Output

Loop     : fib(20) = 6765 (19 loop steps)
Recursion: fib(20) = 6765 (21891 function calls)

Same answer, but the recursive version made 21,891 calls against 19 loop steps. For fib(40) it would make over 300 million calls. See the classic Fibonacci series using recursion program to practise.

Important Points to Remember

  • Recursion = function calls itself; iteration = loop.
  • Recursion uses more memory (stack frames) and is usually slower.
  • Recursion code is often shorter and clearer for tree-like problems.
  • Endless recursion → stack overflow; endless loop → hang.
  • Every recursive solution can be written with a loop (sometimes with an extra stack).

Common Mistakes Students Make

Wrong ideaCorrect idea
Recursion is always fasterUsually slower, due to call overhead and stack use
Some problems can only be solved by recursionAny recursion can be converted to iteration
Recursion uses no extra memoryEvery call adds a stack frame
Recursion is uselessIt is the natural choice for trees, backtracking and divide-and-conquer

Recursion vs Iteration Practice Questions

  1. Write four differences between recursion and iteration.
  2. Why does recursion use more memory?
  3. Why is the naive recursive Fibonacci slow?
  4. Give two problems where recursion is a natural choice.
  5. What happens if a recursive function has no base case? And a loop with no exit?
Show answers
  1. Recursion uses function calls, iteration uses loops; recursion stops at a base case, iteration when the condition is false; recursion uses more memory; recursion is usually slower but often shorter.
  2. Each call creates a new stack frame for its parameters and local variables.
  3. It calculates the same values again and again; the number of calls grows exponentially.
  4. Tree traversal, Tower of Hanoi (also merge sort, quick sort).
  5. Recursion: stack overflow (crash). Loop: infinite loop (program hangs).

Coding Exercise

Write the sum of digits of a number in two ways: with a while loop and with recursion. Test both with 9817 (answer 25).

Show solution
#include <stdio.h>

int digits_loop(int n)
{
    int sum = 0;
    while (n != 0)
    {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int digits_rec(int n)
{
    if (n == 0)
        return 0;
    return n % 10 + digits_rec(n / 10);
}

int main(void)
{
    printf("Loop: %d, Recursion: %d\n", digits_loop(9817), digits_rec(9817));
    return 0;
}
Loop: 25, Recursion: 25

Quick Quiz: Recursion vs Iteration (MCQ)

  1. Which usually uses more memory?

    A) Iteration   B) Recursion   C) Both equal   D) Neither

  2. Endless recursion leads to:

    A) Infinite loop   B) Stack overflow   C) Compile error   D) Nothing

  3. Iteration is done using:

    A) Function calls   B) Loops   C) Pointers   D) Macros

  4. Which is a natural fit for recursion?

    A) Printing 1 to 10   B) Tower of Hanoi   C) Reading one number   D) Adding two numbers

  5. Can every recursive function be written using loops?

    A) Yes   B) No

Show answers
  1. B: recursion.
  2. B: stack overflow.
  3. B: loops.
  4. B: Tower of Hanoi.
  5. A: Yes (sometimes using an explicit stack).

Quick Revision for Exams and Interviews

Read this before your exam. The highlighted words are the answer.

Must-remember facts

RecursionFunction calls itself; stops at base case
IterationLoop; stops when condition is false
MemoryRecursion more (stack frames)
SpeedIteration usually faster
Failure modeRecursion: stack overflow; loop: infinite loop
Recursion best forTrees, Tower of Hanoi, divide and conquer
fib(20) naive calls21,891

Frequently asked questions

Which is better, recursion or iteration?
Iteration for simple repetition (faster, less memory); recursion when the problem is naturally self-similar (trees, divide and conquer).
What are the disadvantages of recursion?
More memory, slower due to call overhead, and risk of stack overflow.
What are the advantages of recursion?
Shorter, cleaner code that matches the mathematical definition.

Remember

  • Stairs: iteration = walk yourself, recursion = ask the next friend.
  • Simple counting → loop; trees → recursion.

Next Topic

Next lesson: Math Functions in C (math.h). You will learn the ready-made maths functions in math.h.