Recursion in C++ with Example

The existence of functions makes possible a programming technique called recursion. Recursion c++ involves a function calling itself. This sounds rather improbable, and indeed a function calling itself is often a bug. However, when used correctly this technique can be surprisingly powerful.

Recursion is much easier to understand with an example than with lengthy explanations, so let’s apply it to a program we’ve seen before: the FACTOR program of before, “Loops and Decisions.” That program used a for loop to calculate the factorial of a number. (See that example for an explanation of factorials.) Our new program, FACTOR2, uses recursion instead of a loop.

//factor2.cpp
//calculates factorials using recursion
#include <iostream>
using namespace std;
unsigned long factfunc(unsigned long); //declaration
int main()
{
int n; //number entered by user
unsigned long fact; //factorial
cout << “Enter an integer: “;
cin >> n;
fact = factfunc(n);
cout << “Factorial of “ << n << “ is “ << fact << endl; 
return 0;
}
//-------------------------------------------------------------
// factfunc()
// calls itself to calculate factorials
unsigned long factfunc(unsigned long n)
{
if(n > 1)
return n * factfunc(n-1); //self call
else
return 1;
}

The output of this program is the same as the FACTOR program in before we posted.

The main() part of FACTOR2 looks reasonable: it calls a function, factfunc(), with an argument that is a number entered by the user. This function then returns the factorial of that number to main().

The function factfunc() is another story. What’s it doing? If n is greater than 1, the function calls itself. Notice that when it does this it uses an argument one less than the argument it was called with. Suppose it was called from main() with an argument of 5. It will call a second version of itself with an argument of 4. Then this function will call a third version with an argument of 3, and so on.

Notice that each version of the function stores its own value of n while it’s busy calling another version of itself.

After factfunc() calls itself four times, the fifth version of the function is called with an argument of 1. It discovers this with the if statement, and instead of calling itself, as previous versions have, it returns 1 to the fourth version. The fourth version has stored a value of 2, so it multiplies the stored 2 by the returned 1, and returns 2 to the third version. The third version has stored 3, so it multiplies 3 by the returned 2, and returns 6 to the second version. The second version has stored 4, so it multiplies this by the returned 6 and returns 24 to the first version. The first version has stored 5, so it multiplies this by the returned 24 and returns 120 to main().

Version          Action         Argument or Return Value
-----------------------------------------------------------
 1                call               5
 2                call               4
 3                call               3
 4                call               2
 5                call               1
 5                return             1
 4                return             2
 3                return             6
 2                return             24
 1                return             120

Every recursive function must be provided with a way to end the recursion in c++. Otherwise it will call itself forever and crash the program. The if statement in factfunc() plays this role, terminating the recursion when n is 1.

Is it true that many versions of a recursive function are stored in memory while it’s calling itself? Not really. Each version’s variables are stored, but there’s only one copy of the function’s code. Even so, a deeply nested recursion can create a great many stored variables, which can pose a problem to the system if it doesn’t have enough space for them.