Recursion in C++

Our example demonstrates recursive functions using a classic factorial calculation and a Fibonacci sequence generator.

#include <iostream>
#include <functional>

// This 'fact' function calls itself until it reaches the
// base case of 'fact(0)'.
int fact(int n) {
    if (n == 0) {
        return 1;
    }
    return n * fact(n-1);
}

int main() {
    std::cout << fact(7) << std::endl;

    // Lambdas can also be recursive, but this requires the
    // lambda to be declared with std::function explicitly
    // before it's defined.
    std::function<int(int)> fib;

    fib = [&fib](int n) {
        if (n < 2) {
            return n;
        }

        // Since 'fib' was previously declared, C++
        // knows which function to call with 'fib' here.
        return fib(n-1) + fib(n-2);
    };

    std::cout << fib(7) << std::endl;

    return 0;
}

To compile and run the program:

$ g++ -std=c++14 recursion.cpp -o recursion
$ ./recursion
5040
13

This example demonstrates two types of recursive functions in C++:

1. A traditional recursive function (fact) that calculates the factorial of a given number.
2. A recursive lambda function (fib) that calculates the Fibonacci sequence.

The fact function is straightforward: it calls itself with n-1 until it reaches the base case of n == 0.

The fib lambda is more complex. In C++, for a lambda to be recursive, we need to use std::function to declare it before defining it. This allows the lambda to refer to itself within its own body.

Both functions demonstrate how recursive algorithms can be implemented in C++, showcasing the language’s support for this powerful programming concept.