Chapter 16 of 37

Recursion

On this page

Sometimes a function needs to call itself to solve a problem.

This technique is called recursion.

What is Recursion?

Recursion is a technique where a function calls itself repeatedly until a specific condition stops it.

For example:

void count(int n)
{
    if (n == 0)
        return;

    printf("%d\n", n);
    count(n - 1);
}

If we call:

count(5);

The output will be:

Here, count() keeps calling itself with a smaller value.

Two Important Parts of Recursion

Every recursive function generally needs two things:

1. Base Case

The base case tells the function when to stop.

if (n == 0)
    return;

Without a proper base case, the function may keep calling itself indefinitely.

2. Recursive Case

The recursive case is where the function calls itself.

count(n - 1);

So the basic idea is:

Function
   ↓
Check base case
   ↓
Not reached?
   ↓
Call itself
   ↓
Smaller problem
   ↓
Repeat

Example: Factorial

Recursion is commonly used to calculate factorials.

The factorial of 5 is:

5 × 4 × 3 × 2 × 1 = 120

We can write it recursively:

int factorial(int n)
{
    if (n == 1)
        return 1;

    return n * factorial(n - 1);
}

Calling:

printf("%d", factorial(5));

produces:

The calls work like this:

factorial(5)
    ↓
5 × factorial(4)
        ↓
      4 × factorial(3)
              ↓
            3 × factorial(2)
                    ↓
                  2 × factorial(1)
                          ↓
                          1

Then the results return back up to produce 120.

Recursion vs Loop

Many recursive problems can also be solved using loops.

Recursion	Loop
Function calls itself	Repeats using a loop
Uses function call stack	Usually uses less memory
Can make some problems easier to express	Often simpler and more efficient
Useful for trees, graphs, divide-and-conquer, etc.	Useful for straightforward repetition

Recursion is especially useful when a problem naturally breaks into smaller versions of itself, such as tree traversal, searching, and divide-and-conquer algorithms.

In Simple Words

Recursion means a function calling itself to solve a smaller version of the same problem.

Just remember two things:

Base case → stops the recursion

Recursive case → calls the function again

Without a proper stopping condition, recursion can continue until the program runs out of call-stack space.

PreviousFunctions NextArrays