Recursion in C

Recursion occurs when a function calls itself directly or indirectly.

void show()
{
    show();
}

Here, the function show() calls itself. This is a simple example of recursion, but it has no stopping condition.

A function that calls itself is called a recursive function.

void count(int number)
{
    if (number == 0)
    {
        return;
    }

    printf("%d\n", number);

    count(number - 1);
}

The function continues by calling itself with a smaller value.

The base case is the condition that stops the recursive calls.

void count(int number)
{
    if (number == 0)
    {
        return;
    }

    printf("%d\n", number);

    count(number - 1);
}

Here, number == 0 is the base case.

The recursive case is the part of the function that calls the same function again.

void count(int number)
{
    if (number == 0)
    {
        return;
    }

    printf("%d\n", number);

    count(number - 1);
}

The statement count(number - 1) is the recursive case.

#include <stdio.h>

void countDown(int number)
{
    if (number == 0)
    {
        return;
    }

    printf("%d\n", number);

    countDown(number - 1);
}

int main()
{
    countDown(5);

    return 0;
}

Output:

5
4
3
2
1

Suppose we call countDown(3).

countDown(3)
    ↓
countDown(2)
    ↓
countDown(1)
    ↓
countDown(0)
    ↓
return

When the base case is reached, the recursive calls stop.

Each function call creates a new stack frame. Recursive calls continue creating stack frames until the base case is reached.

count(3)
count(2)
count(1)
count(0)

After reaching the base case, the calls return in reverse order.

Factorial is one of the most common examples of recursion.

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

    return number * factorial(number - 1);
}

For example:

5! = 5 × 4 × 3 × 2 × 1 = 120

#include <stdio.h>

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

    return number * factorial(number - 1);
}

int main()
{
    printf("Factorial = %d", factorial(5));

    return 0;
}

Output:

Factorial = 120

For factorial(4), the recursive calls can be viewed as:

factorial(4)
4 × factorial(3)
4 × 3 × factorial(2)
4 × 3 × 2 × factorial(1)
4 × 3 × 2 × 1 × factorial(0)
4 × 3 × 2 × 1 × 1
24

The final result is 24.

int sum(int number)
{
    if (number == 0)
    {
        return 0;
    }

    return number + sum(number - 1);
}

Calling sum(5) calculates:

5 + 4 + 3 + 2 + 1 = 15

#include <stdio.h>

int sum(int number)
{
    if (number == 0)
    {
        return 0;
    }

    return number + sum(number - 1);
}

int main()
{
    int result = sum(5);

    printf("Sum = %d", result);

    return 0;
}

Output:

Sum = 15

void countdown(int number)
{
    if (number <= 0)
    {
        return;
    }

    printf("%d\n", number);

    countdown(number - 1);
}

The function prints a number and then calls itself with a smaller value.

void countUp(int number)
{
    if (number == 0)
    {
        return;
    }

    countUp(number - 1);

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

Here the recursive call occurs before the printf(), so the numbers are printed in increasing order.

The Fibonacci sequence is another common example of recursion.

int fibonacci(int number)
{
    if (number <= 1)
    {
        return number;
    }

    return fibonacci(number - 1)
         + fibonacci(number - 2);
}

This implementation directly follows the recursive definition of the Fibonacci sequence.

#include <stdio.h>

int fibonacci(int number)
{
    if (number <= 1)
    {
        return number;
    }

    return fibonacci(number - 1)
         + fibonacci(number - 2);
}

int main()
{
    for (int i = 0; i < 8; i++)
    {
        printf("%d ", fibonacci(i));
    }

    return 0;
}

Output:

0 1 1 2 3 5 8 13

int power(int base, int exponent)
{
    if (exponent == 0)
    {
        return 1;
    }

    return base * power(base, exponent - 1);
}

For example, power(2, 4) calculates 2 × 2 × 2 × 2, giving 16.

The greatest common divisor can be calculated recursively using the Euclidean algorithm.

int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }

    return gcd(b, a % b);
}

The recursion stops when the second value becomes zero.

#include <stdio.h>

int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }

    return gcd(b, a % b);
}

int main()
{
    printf("GCD = %d", gcd(48, 18));

    return 0;
}

Output:

GCD = 6

A string length can also be calculated recursively using a pointer.

int length(char str[])
{
    if (str[0] == '\0')
    {
        return 0;
    }

    return 1 + length(str + 1);
}

The function moves through the string one character at a time until it reaches the null character.

Recursion can be used to process a string and print its characters in reverse order.

void reversePrint(char str[])
{
    if (str[0] == '\0')
    {
        return;
    }

    reversePrint(str + 1);

    printf("%c", str[0]);
}

The recursive call occurs before printing, so characters are printed while the calls return.

int arraySum(int numbers[], int size)
{
    if (size == 0)
    {
        return 0;
    }

    return numbers[size - 1]
         + arraySum(numbers, size - 1);
}

The function processes one array element during each recursive call.

#include <stdio.h>

int arraySum(int numbers[], int size)
{
    if (size == 0)
    {
        return 0;
    }

    return numbers[size - 1]
         + arraySum(numbers, size - 1);
}

int main()
{
    int numbers[] = {10, 20, 30, 40};

    printf("Sum = %d",
           arraySum(numbers, 4));

    return 0;
}

Output:

Sum = 100

There are two common forms of recursive calls.

• Direct recursion: A function calls itself directly.
• Indirect recursion: One function calls another function, which eventually calls the first function.

void A()
{
    B();
}

void B()
{
    A();
}

This example shows the basic structure of indirect recursion. A suitable stopping condition is required.

Many recursive problems can also be solved using loops.

Using a loop:

int factorial(int number)
{
    int result = 1;

    for (int i = 1; i <= number; i++)
    {
        result *= i;
    }

    return result;
}

A recursive solution may be more natural for problems that are defined in terms of smaller versions of the same problem.

Every recursive call uses stack space. If recursion continues too deeply, the program can run out of stack space.

void test()
{
    test();
}

This function has no base case, so it keeps calling itself. Recursive functions should have a reachable stopping condition.

• Forgetting the base case.
• Using a base case that can never be reached.
• Not moving the input toward the base case.
• Using recursion unnecessarily for a simple problem.
• Creating very deep recursion and exhausting stack space.
• Returning the wrong result from a recursive call.

int count(int number)
{
    if (number == 0)
    {
        return 0;
    }

    return 1 + count(number - 1);
}

Always check how each recursive call moves toward the stopping condition.

#include <stdio.h>

int factorial(int number)
{
    if (number <= 1)
    {
        return 1;
    }

    return number * factorial(number - 1);
}

int main()
{
    int number;

    printf("Enter a number: ");
    scanf("%d", &number);

    if (number < 0)
    {
        printf("Factorial is not defined for negative numbers.");
    }
    else
    {
        printf("Factorial = %d",
               factorial(number));
    }

    return 0;
}

Recursion can be useful when a problem naturally consists of smaller versions of the same problem.

• Factorial calculations
• Fibonacci calculations
• Tree-like structures
• Divide-and-conquer algorithms
• Recursive searching and processing
• Problems that can be divided into smaller similar problems

For simple repeated calculations, a loop may often be easier to understand and more memory-efficient.

Practice the following programs:

1. Print numbers from N to 1 using recursion.
2. Print numbers from 1 to N using recursion.
3. Calculate factorial using recursion.
4. Calculate the sum of numbers from 1 to N.
5. Calculate the power of a number recursively.
6. Generate Fibonacci numbers using recursion.
7. Find the GCD of two numbers recursively.
8. Find the sum of array elements recursively.
9. Find the length of a string recursively.
10. Print a string in reverse using recursion.

For every recursive program, identify the base case and the recursive case before writing the code.