Search⌘ K
AI Features
Home
Courses
Recursion for Coding Interviews in C++

Computing Factorials

Explore how to compute factorials using recursion in C++. Learn the concept of factorials, understand the base and recursive cases in the function, and see step-by-step code implementation to solidify your understanding for coding interviews.

We'll cover the following...

What is a factorial?

A factorial is the product of an integer and all the positive integers less than it. It is denoted by the symbol: !!

For example, 4! (read as four factorial) is denoted as follows:

4!=4×3×2×1=244!=4\times3\times2\times1=24

6!=6×5×4×3×2×1=7206!=6\times5\times4\times3\times2\times1=720

Expanding a Factorial

A factorial of any integer can be written as a product of that integer and the factorial of the integers less than it. For example, 6!6! can be written as follows:

6!=6×5!6!=6\times5!

6!=6×5×4!6!=6\times5\times4!

6!=6×5×4×3!6!=6\times5\times4\times3!

6!=6×5×4×3×2!6!=6\times5\times4\times3\times2!

6!=6×5×4×3×2×16!=6\times5\times4\times3\times2\times1

Important Note: Factorials only exists for positive numbers. The factorial of 0 is equal to 1.

Mathematical Notation

The factorial of a number can be written in the form shown below:

n!=n×(n−1)!n!=n\times(n-1)!

The generic mathematical notation for computing a factorial is:

n!=(n)×(n−1)×(n−2)×(n−3)×(n−4)....(3)×(2)×(1)n!=(n)\times(n-1)\times(n-2)\times(n-3)\times(n-4)....(3)\times (2)\times(1)

We will now use the recursive function concept for computing the factorial of a number.

Code Implementation

The code below shows how to implement a factorial with recursion. First, let’s look at the code, then we can go on to its explanation.

Try changing the value of “input” below in order to see different outputs

C++
#include <iostream>
using namespace std;
// defining the function
double factorial(int n)
{
  // base case
  if ((n==0) || (n==1))
  {
    return 1;
  }
  // recursive case
  else
  {
    return n*factorial(n-1);
  }
}
int main() 
{
  // defining the input
  int input= 6;
  // calling the function and printing the output
  double result=factorial(input);
  cout<<input<<"! = "<<result;
}

Understanding the code

In the code above, the function, factorial, is a recursive function as it makes a recursive call. Below is an explanation of the above code:

Driver Function

  • Inside the int main() code, we have defined an integer variable, at line 21, named input.

  • In the next line, line 23, we are computing the factorial using the function factorial, and storing the answer returned from it in the variable, result. The data type of result is double, which is the same as the return type of the function factorial.

  • In line 24, we are printing the computed factorial.

Recursive Function

To cater for large factorials, in line 4, we have specified the return type of this function as double. This function takes an integer, n, as the input argument.

Base Case
  • The base case of the function is being defined in line 7 where the function will terminate and return 1 when the if condition of n==0 or n==1 is met. This is because the factorial of 00 or 11 is equal to 11 and a factorial cannot go below this.
Recursive Case

  • If the base case condition does not evaluate to true, the function then enters the else block where it recursively calls itself with the input argument n-1 instead of n, as seen in line 14. This is because of the following factorial expansion:

    n!=n×(n−1)!n!=n\times (n-1)!

Understanding Through a Stack

Now that you have learned about computing factorial using recursion, we will solve another interesting mathematical problem in the next lesson, the sum of integers from 1 to n.