C++: Finding Factorials using Recursion

Yet another easy program to try and code would be one that can generate the factorials of numbers. It’s not that quite difficult and an iteration based approach using the fundamental looping statements (for loop for example) can easily help resolve the program.

But we’re going to take a different approach today – using recursion. Recursion is the technique of invoking a function inside its own body creating multiple function calls of itself in the function call stack until a base value is found when the recursion terminates. It’s just like iteration but the only change is that we’re making the iteration using a different feature of C++. While recursions are not normally used due to heavy overheads in memory, it’s good to get to know about it and this program is one of the many simple applications of recursion.

Source Code

#include <iostream>
#include <conio.h>
using namespace std;
int factorial(int);
void main()
{
 int num;
 cout << "\nEnter the limit of factorial table: ";
 cin >> num;
 cout << "\nThe factorials of first " << num << " numbers are:\n";
 for (int i = 0; i <= num; i++)
  cout << '\n' << i << "! = " << factorial(i);
 _getch();
}
int factorial(int num)
{
 if (num == 0)
  return 1;
 else
  return num * factorial(num - 1);
}

Analysis

In our program, we are outputting a table of factorial values for numbers from 0 to num, which is the variable whose value will be inputted by the user. We use an iteration statement to call the recursive function for each value of i from 0 to num.

The technique of recursion can be better understood by plotting a diagram of each recursive calls. Suppose if 5 is the value of i passed to the recursive function. In the first function call, the number 5 itself is sent as the argument. Inside the function, 5 gets multiplied to the value returned by the same function in an else statement. But this time, the number 4 gets passed as the argument. This goes on until the value of num becomes 1 which is the base case of the recursion. At this point, recursion breaks and one by one, the values get returned until the first function call is reached. By this time, the return statements would’ve formed a chain of numbers multiplied to each other. In this case, it’d be 1 x 2 x 3 x 4 x 5. Thus, the value 120 gets returned to the main loop body where the value of 5! is outputted as 120.

You can better understand the mechanism by the recursion diagram where you can observe how function call stacks get filled up with the copies of the same function (the function’s arguments to be exact). Hence, it’s easy to build programs using the technique of recursion. Well, most of the programs you practised while studying iteration can be implemented using recursion though it needs planning too.

But there’s a serious drawback for recursion. It creates heavy overhead in the memory by creating multiple copies of the function itself. Each level of recursion has a doubling effect on the number of function calls. Technically speaking, it’d require about a million function calls to calculate the factorial of 20 and the number would go on increasing as we go higher and higher. Computer scientists define this problem as exponential complexity. This drastically slows down the program when bigger numbers are approached. The efficiency would depend on the processing power of the computer. Hence, it’s not advisable to use recursion for such programs. The fact that they slow down the program is the main reason why recursive techniques are less preferred and even they do get a preference, it’d be for such a program which guarantees the use of very small numbers.

Hence, use recursion wisely. You can understand the effect by inputting greater values such as 30 or above and see how much time it takes to produce the final output. It’s also good to understand the time it takes to finish on different machines.