Recursion in C++

Recursion occurs when a function calls itself directly or indirectly.

void countDown(int number) {

    if (number == 0) {
        return;
    }

    std::cout << number << std::endl;

    countDown(number - 1);
}

Here, countDown() calls itself with a smaller value.

A recursive function generally performs these steps:

1. Receives an input.
2. Checks the base case.
3. If the base case is not reached, performs some work.
4. Calls itself with a smaller or simpler input.
5. Eventually reaches the base case.

The function calls are stored in memory until the recursive process finishes.

#include <iostream>

void message(int number) {

    if (number == 0) {
        return;
    }

    std::cout << "Hello" << std::endl;

    message(number - 1);
}

int main() {

    message(3);

    return 0;
}

Output:

Hello
Hello
Hello

The base case is the condition that stops a recursive function.

void count(int number) {

    if (number == 0) {
        return;
    }

    std::cout << number;

    count(number - 1);
}

In this example, number == 0 is the base case.

The recursive case is the part where the function calls itself.

void count(int number) {

    if (number == 0) {
        return;
    }

    std::cout << number << std::endl;

    count(number - 1);
}

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

void countDown(int number) {

    if (number == 0) {
        return;
    }

    std::cout << number << std::endl;

    countDown(number - 1);
}

int main() {

    countDown(5);

    return 0;
}

Output:

5
4
3
2
1

void countUp(int number) {

    if (number == 0) {
        return;
    }

    countUp(number - 1);

    std::cout << number << std::endl;
}

int main() {

    countUp(5);

    return 0;
}

Output:

1
2
3
4
5

The position of the recursive call affects the output order.

Factorial is a common example of recursion.

int factorial(int number) {

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

    return number * factorial(number - 1);
}

int main() {

    std::cout << factorial(5);

    return 0;
}

Output:

120

The calculation is based on: 5 × 4 × 3 × 2 × 1 = 120.

For factorial(5), the function calls itself like this:

factorial(5)
5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1 * factorial(0)

When factorial(0) returns 1, the previous calls can complete their calculations.

A recursive function can return a value just like a normal function.

int sum(int number) {

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

    return number + sum(number - 1);
}

For example, sum(5) returns:

5 + 4 + 3 + 2 + 1 = 15

int sum(int number) {

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

    return number + sum(number - 1);
}

int main() {

    int result = sum(10);

    std::cout << "Sum = "
              << result;

    return 0;
}

Output:

Sum = 55

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);
}

int main() {

    std::cout << fibonacci(6);

    return 0;
}

For this example, the result is:

8

void printNumbers(int number) {

    if (number > 10) {
        return;
    }

    std::cout << number << " ";

    printNumbers(number + 1);
}

int main() {

    printNumbers(1);

    return 0;
}

Output:

1 2 3 4 5 6 7 8 9 10

void reverseNumbers(int number) {

    if (number == 0) {
        return;
    }

    std::cout << number << " ";

    reverseNumbers(number - 1);
}

int main() {

    reverseNumbers(10);

    return 0;
}

Output:

10 9 8 7 6 5 4 3 2 1

int power(int base, int exponent) {

    if (exponent == 0) {
        return 1;
    }

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

int main() {

    std::cout << power(2, 4);

    return 0;
}

Output:

16

The function calculates 2 × 2 × 2 × 2.

A recursive function can have multiple parameters.

int power(int base, int exponent) {

    if (exponent == 0) {
        return 1;
    }

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

Here, base stays the same while exponent gets smaller with every recursive call.

The Greatest Common Divisor (GCD) can be calculated recursively.

int gcd(int a, int b) {

    if (b == 0) {
        return a;
    }

    return gcd(b, a % b);
}

int main() {

    std::cout << gcd(48, 18);

    return 0;
}

Output:

6

Recursion can also be used to process characters of a string one by one.

#include <iostream>
#include <string>

void printString(std::string text, int index) {

    if (index == text.length()) {
        return;
    }

    std::cout << text[index] << std::endl;

    printString(text, index + 1);
}

The index increases until it reaches the end of the string.

Each function call is stored on the program's call stack. When a recursive function calls itself, a new function call is added to the stack.

void test(int number) {

    if (number == 0) {
        return;
    }

    test(number - 1);
}

When the base case is reached, the calls return one by one.

A recursive function without a proper stopping condition can continue calling itself.

void test() {

    test();
}

This function has no base case. It can continue making function calls until the available stack memory is exhausted.

When a function directly calls itself, it is called direct recursion.

void count(int number) {

    if (number == 0) {
        return;
    }

    count(number - 1);
}

The function count() directly calls itself.

Indirect recursion occurs when one function calls another function and that function eventually calls the first function again.

void second();

void first(int number) {

    if (number == 0) {
        return;
    }

    second();
}

void second() {

    first(0);
}

Here, the functions are connected through each other.

Recursion can be useful for problems that naturally contain smaller versions of the same problem.

• Tree traversal.
• Graph algorithms.
• Divide-and-conquer algorithms.
• Backtracking problems.
• Mathematical problems such as factorial.
• Problems involving nested structures.

int sumDigits(int number) {

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

    return (number % 10)
         + sumDigits(number / 10);
}

int main() {

    std::cout << sumDigits(1234);

    return 0;
}

Output:

10

The digits are processed as 4 + 3 + 2 + 1.

• Forgetting the base case.
• Using an incorrect base case.
• Not moving toward the base case.
• Passing the wrong value to the recursive call.
• Creating unnecessarily deep recursion.
• Using recursion when a simple loop is clearer.
• Ignoring memory usage caused by recursive calls.

#include <iostream>

int factorial(int number) {

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

    return number * factorial(number - 1);
}

int main() {

    int number;

    std::cout << "Enter a number: ";
    std::cin >> number;

    std::cout << "Factorial = "
              << factorial(number);

    return 0;
}

This program takes a number from the user and calculates its factorial using recursion.

#include <iostream>

int sum(int number) {

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

    return number + sum(number - 1);
}

int main() {

    int number;

    std::cout << "Enter a number: ";
    std::cin >> number;

    std::cout << "Sum = "
              << sum(number);

    return 0;
}

• Always define a clear base case.
• Make sure every recursive call moves toward the base case.
• Keep recursive functions simple and focused.
• Choose meaningful parameter names.
• Consider memory usage for deep recursion.
• Use iteration when it is simpler and more appropriate.
• Test small inputs before testing large inputs.

returnType functionName(parameters) {

    if (baseCondition) {
        return result;
    }

    return functionName(smallerProblem);
}