Recursion in C++ programming

Definition of recursive function

A recursive function is one that calls itself. You have seen instances of functions calling other functions. Function A can call function B, which can then call Function C. It’s also possible for a function to call itself. A function that calls itself is a recursive function.

Look at this message function:

    void message()
    {
    cout << "This is a recursive function.\n";
    message();
    }

This function displays the string "This is a recursive function.\n", and then calls itself. Each time it calls itself, the cycle is repeated.

There’s no way to stop the recursive calls. This function is like an infinite loop because there is no code to stop it from repeating. To be useful, a recursive function must have a way of controlling the number of recursive calls.

The following is a modification of the message function. It passes an integer argument that holds the number of times the function is to call itself.

    void message(int times)
    {
    if (times > 0)
    {
    cout << "This is a recursive function.\n";
    message(times - 1);
    }   
    }

This function contains an if statement that controls the recursion. As long as the times argument is greater than zero, it will display the message and call itself again. Each time it calls itself, it passes times - 1 as the argument.

The program demonstrates the recursive message function, modified to show the value of the parameter to each call.

    #include <iostream>
    using namespace std;
    void message(int);
    int main() {
    message(3);
    return 0;
    }
    void message(int times)
    {
    if (times > 0)
    {
    cout << "Message " << times << "\n";
    message(times - 1);
    }
    }

    Program Output :
    Message 3
    Message 2
    Message 1

Recursive functions work by breaking a complex problem down into subproblems of the same type. This breaking down process stops when it reaches a base case, that is, a subproblem that is simple enough to be solved directly.

For example, in the recursive message function of the preceding examples, the base case is when the parameter times is 0.

    #include <iostream>
    using namespace std;
    
    // Function prototype
    void message(int);
    int main()  {
    message(3);
    return 0;
    }
    void message(int times) {
    cout << "Message " << times << ".\n";
    if (times > 0)
    {
    message(times - 1);
    }
    cout << "Message " << times << " is returning.\n";
    }

    Program Output :
    Message 3.
    Message 2.
    Message 1.
    Message 0.
    Message 0 is returning.
    Message 1 is returning.
    Message 2 is returning.
    Message 3 is returning.