Recursion

A recursive function in C++ is a function that calls itself. Here is an example of it:

#include <iostream>

void countDown(int count)
{
    std::cout << "push " << count << '\n';
    countDown(count-1); // countDown() calls itself recursively
}

int main()
{
    countDown(5);

    return 0;
}

When countDown(5) is called “push 5” is printed, and countDown(4) is called.

countDown(4) prints “push 4” and calls countDown(3). countDown(3) prints “push 3” and calls countDown(2). The sequence of countDown(n) calling countDown(n-1) is repeated indefinitely, effectively forming the recursive equivalent of an infinite loop.

As we already learnt that every function call causes data to be placed on the call stack. Because countDown() function never returns (it just calls contDown() again), this information is never being popped off the stack, stack overflow will result, and the program will crash or terminate.

Recursive termination conditions

Recursive function calls generally work just like function calls. However, the program above illustrates the most important difference with recursive functions: you must include a recursive termination condition, or they will run “forever” (actually, until the call stack runs out of memory). A recursive termination is a condition that, when met, will cause the recursive function to stop calling itself.

Recursive termination generally involves using an if statement. Here is our function redesigned with a termination condition.

#include <iostream>

void countDown(int count)
{
    std::cout << "push " << count << '\n';

    if (count > 1) // termination condition
        countDown(count-1);

    std::cout << "pop " << count << '\n';
}

int main()
{
    countDown(5);
    return 0;
}

Now when we run our program, countDown() will start by outputting the following:

push 5
push 4
push 3
push 2
push 1
pop 1
pop 2
pop 3
pop 4
pop 5

If we were to look at the call stack at this point, we would see the following:

countDown(1)
countDown(2)
countDown(3)
countDown(4)
countDown(5)
main()

Because of the termination condition, countDown(1) does not call countDown(0).

Instead, the if statement does not execute, so it prints “pop1” and then terminates. At this point, countDown(1) is popped off the stack, and control returns to countDown(2).

countDown(2) resumes execution at the point after countDown(1) was called, so it prints “pop 2” and then terminates. The recursive function calls get subsequently popped off until all instances of countDown have been removed.

Thus, this program in total outputs:

push 5
push 4
push 3
push 2
push 1
pop 1
pop 2
pop 3
pop 4
pop 5

It's worth noting that the “push” outputs happen in forward order since they occur before the recursive function call.The “pop" outputs occur in reverse order because they occur after the recursive function call, as the functions are being popped off the stack (which happens in the reverse order that they were put on).