Recursion

A function can call itself. That is recursion. All function calls get their own fresh set of arguments and local variables, just as if a different function entirely had been called. The current call stack keeps all active calls alive until each returns.

The most critical point in designing recursive functions is to have at least one base case, a condition where the functions stop calling themselves. If the function never reaches a base case, the calls would continue on forever, the stack would overflow, and the program would crash.

#include <iostream>

void countdown(int n)
{
    if (n <= 0)
    {
        std::cout << "Done\n";
        // Exit the function early when this condition is met
        return;
    }

    std::cout << n << '\n';
    countdown(n - 1);
}

int main()
{
    countdown(3);
}

Starting a recursive countdown with a value of 3. The parameter takes on the value 3. The function checks the base case, but it returns false. Hence the program executes this value and the function is called with 2.

Now this second call also receives its own parameter with a value of 2. It executes this value and then calls again with 1. The third call of the function executes the value 1 and then calls the function with 0.

Now the base case test returns true and the deepest call returns. It then returns to the above waiting call, which finishes and returns itself. Then the same continues until the first call is returned.

Each step in the stack keeps one of the parameter values copied into its local variable. If the parameter value is changed in a call then it will never affect another function call.

This is the same as pass by value, the only difference is that a function name can be reused for recursive calling.

When a base case of a recursive function is either missed or unreachable, then there is no limit to the stack growth. As each recursive call uses a new stack frame and since stack has limited memory, there comes a boundary condition when memory is exhausted.

C++ does not have a mechanism to detect infinite loops during compile time.

#include <iostream>

void bad_countdown(int n)
{
    std::cout << n << '\n';
    bad_countdown(n - 1);
}

int main()
{
    // bad_countdown(3);
}

The runtime error that occurs is overflow of call stack.

For that you must have at least one base case which is guaranteed to reach the state.

We can even create results of a function call which come back to the original call via the stack after the calls themselves have been returned. One case for this is factorials.

A call on 5 then depends on call 4, which depends on call 3, until the base is reached.

#include <iostream>

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

    return n * factorial(n - 1);
}

int main()
{
    std::cout << "5! is " << factorial(5) << '\n';
}

This base case is computed and the result sent back to call 4, which can now finish its own computation based on the result from call 3.

This happens with every awaiting call until the first one which returns the value that will eventually get back to the original call.

Each function waits for a call to return the results, in order to compute its own values and again return.

Maximum recursion depth depends on stack size. A small number of parameters and small inputs will take a short time/number of calls and also limited stack size would suffice. 

However, huge input parameters in recursive calls for recursive functions will create an exceptionally large number of stack frames which can even exceed the stack limit even though there is an accurate base case check.

Recursion involves taking many small independent calls, all carrying with them values that, when combined, result in the total computation.

These calls exist independently until the base case returns a value and these return values are then used to assemble a final result.

#include <iostream>

void countdown(int n)
{
    if (n <= 0)
    {
        std::cout << "Done\n";
        // Exit the function early when this condition is met
        return;
    }

    std::cout << n << '\n';
    countdown(n - 1);
}

int main()
{
    countdown(3);
}

#include <iostream>

void countdown(int n)
{
    if (n <= 0)
    {
        std::cout << "Done\n";
        // Exit the function early when this condition is met
        return;
    }

    std::cout << n << '\n';
    countdown(n - 1);
}

int main()
{
    countdown(3);
    countdown(2);
}

3
2
1
Done
2
1
Done