Factorial of a Number : Iterative and Recursive

Problem Statement: Given a number X,  print its factorial.

To obtain the factorial of a number, it has to be multiplied by all the whole numbers preceding it. More precisely X! = X*(X-1)*(X-2) … 1.

Note: X  is always a positive number. 

Examples:

Example 1:
Input: X = 5
Output: 120
Explanation: 5! = 5*4*3*2*1

Example 2:
Input: X = 3
Output: 6
Explanation: 3!=3*2*1

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Iterative

Approach:

Since the factorial of X  will be the product of the number itself and all its preceding numbers we can run loop i, from 1 to X. In every iteration current i, is multiplied with the product so far.  

Code:

C++ Code

#include <iostream>
using namespace std;
int factorial(int X) {
   int ans = 1;
   for (int i = 1; i <= X; i++) {
      ans = ans * i;
   }
   return ans;
}
int main() {
   int X = 5;
   int result = factorial(X);
   cout << "The factorial of " << X << " is " << result;
}

Output: The factorial of 5 is 120

Time Complexity: O(n)

Space Complexity: O(1)

Java Code

public class Main {
   static int factorial(int X) {
      int ans = 1;
      for (int i = 1; i <= X; i++) {
         ans = ans * i;
      }
      return ans;
   }
   public static void main(String[] args) {

      int X = 5;
      int result = factorial(X);
      System.out.println("The factorial of " + X + " is " + result);
   }
}   

Output: The factorial of 5 is 120

Time Complexity: O(n)

Space Complexity: O(1)

Solution 2: Recursive

Approach: To apply recursion we have to decompose the larger problem into a smaller problem. In the process of decomposition, the smaller problem should eventually lead to the base case. 

Factorial of X can also be written as X*(X-1)!

Again (X-1)! = (X-1)*(X-2)!

Therefore a smaller instance of the same problem contributes to the original larger problem.

Now that we have understood the basic thought process let’s understand how to solve it:-

  • Make a function to compute factorial that accepts an integer as parameter.
  • Continue to recursively call (X-1)! 
  • Stop when X = 0. Factorial of 0 is 1.Since we already know the answer to this sub problem this will be our base case. 

Code:

C++ Code

#include <iostream>
using namespace std;
int factorial(int X) {
   if (X == 0) {
      return 1;
   }
   return X * factorial(X - 1);
}
int main() {
   int X = 5;
   int result = factorial(X);
   cout << "The factorial of " << X << " is " << result;
}

Output: The factorial of 5 is 120

Time Complexity: O(n) 

Space Complexity:  O(1)

Java Coding

public class Main {
   static int factorial(int X) {
      if (X == 0) {
         return 1;
      }
      return X * factorial(X - 1);
   }
   public static void main(String[] args) {

      int X = 5;
      int result = factorial(X);
      System.out.println("The factorial of " + X + " is " + result);
   }
}

Output: The factorial of 5 is 120

Time Complexity: O(n) 

Space Complexity:  O(1)

Special thanks to Somparna Chakrabarti for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article