C Recursion

Recursion in C means a function calls itself to solve a smaller version of the same problem. A recursive function must have a stopping condition, called a base case, so the calls eventually end.

Recursion is useful when a task naturally breaks into repeated smaller steps, such as counting down, walking through nested data, or calculating a mathematical sequence.

Base Case And Recursive Case

Every recursive function needs two important parts:

• Base case: the condition where the function stops calling itself.
• Recursive case: the part where the function calls itself with a smaller or simpler input.

Here is a classic example that calculates a factorial. The factorial of 5 is 5 * 4 * 3 * 2 * 1.

#include <stdio.h>

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

    return n * factorial(n - 1);
}

int main(void)
{
    printf("5! = %d\n", factorial(5));

    return 0;
}

Output:

5! = 120

The base case is if (n == 0). When n reaches 0, the function returns 1 and stops making more recursive calls. The recursive case is return n * factorial(n - 1);, which calls the same function with a smaller value.

How Recursive Calls Return

Recursive calls build up first, then return in reverse order. The computer must finish the deepest call before earlier calls can finish.

#include <stdio.h>

void countDown(int number)
{
    if (number == 0) {
        printf("Done\n");
        return;
    }

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

int main(void)
{
    countDown(3);

    return 0;
}

Output:

3
2
1
Done

When countDown(3) runs, it prints 3, then calls countDown(2). That continues until number is 0. At that point, the base case prints Done and returns.

Returning A Recursive Result

A recursive function can return a value that depends on the result of a smaller call. This example adds all integers from 1 through n.

#include <stdio.h>

int sumTo(int n)
{
    if (n == 1) {
        return 1;
    }

    return n + sumTo(n - 1);
}

int main(void)
{
    printf("Sum: %d\n", sumTo(4));

    return 0;
}

Output:

Sum: 10

The call sumTo(4) becomes 4 + sumTo(3). Then sumTo(3) becomes 3 + sumTo(2), and so on until the base case returns 1.

Avoid Endless Recursion

If the base case is missing or the argument never moves toward the base case, the function will keep calling itself. That can crash the program because each active function call uses memory on the call stack.

For beginner programs, make sure the recursive call uses a value that gets closer to the base case, such as n - 1 when the base case checks for 0 or 1.

Quick Rules

• Write the base case before the recursive call when possible.
• Make each recursive call work on a smaller or simpler input.
• Use return when the recursive function produces a value.
• Use loops instead of recursion when a loop is simpler and easier to read.
• Test recursive functions with small inputs first.

The key idea is that recursion solves a problem by calling the same function on a smaller problem until a base case stops the calls.