Find the Factorial of the Number using Recursion in Java

Last Updated on May 16, 2023 by Prepbytes

The product of all-natural integers from 1 to N is the factorial of the number N. Factorial is represented by the sign! in mathematics. If we were to multiply the number 5 by its factorial, the answer would be 5!=1×2×3×4×5=120.
There are many ways to calculate a number’s factorial. In this post, we’ll talk about how to use Java’s recursive method to determine a number’s factorial.

What is a Factorial Number?

A number’s factor is represented by the symbol n! and is defined as the product of all positive descending integers. The following recursive formula can be used to calculate the factorial, where the recursive call is made to a multiplicity of all the numbers smaller than the number for which the factorial is computed:

n! = n * [(n-1)!]

i.e factorial of n (n!) = n * (n-1) * ......* 3 * 2* 1

Note: Factorial of 0 will be 1.

How Recursion Works?

Let’s talk quickly about recursion before we get to the main topic. Recursion is a way of solving problems where a function is called inside of itself. By breaking a problem down into smaller subproblems, recursion can solve each one by calling the same method repeatedly. The final solution is created by combining the answers to these subproblems.

Since the product of all the numbers from 1 to N makes up a number’s factorial, N. The simplest method for figuring out the factorial of any number N is:

• Initialize the result variable to 1.
• Run a for loop from 1 to N, multiplying each number with the result variable to update it.

How to Find the Factorial of the Number using Recursion in Java?

Recursion is defined as calling a function within a function. We can compute the number’s factorial using this characteristic. Let’s use an example to better understand how to find factorial using recursion.

Consider the number 5, then determine its factorial. The factorial of 5 is the product of 5 and the factorial of (5!=4!×5), to put it simply. In a similar vein, writing:

4!=3!×4
3!=2!×3
2!=1!×2
The factorial of 1 is also 1, therefore.

Algorithm for Finding the Factorial of the Number using Recursion in Java

• We can use a recursive function and pass the number 5 within the factorial function to determine the factorial of the number 5.
• When the factorial of number 4 has been calculated, we will simply return the value of 5×4! instead of making a recursive call to calculate the factorial until the number equals zero!
• We’ll use the recursive procedure once more to get the factorial of 4. The process will keep on till the number is zero.
• Therefore, since the factorial of zero is 1, we will only return 1 when the number hits zero. You can learn how to calculate the factorial by using the following pseudo-code.

Pseudo Code to Find the Factorial of the Number using Recursion in Java

int factorial(int n)
    // if n <= 0 then return 1
    if (n <= 0)
        return 1
    // calling the recursive function
    // returning the product of (n-1)! and n, as n = (n-1)! × n
    return factorial(n - 1) * n

Let’s put the aforementioned pseudo-code into practice in Java to determine the factorial of any number N.

Code Implementation to Find the Factorial of the Number using Recursion in Java

class Factorial {

  static int factorial(int n) {
    // base case
    if (n == 0) {
      return 1;
    }
    // calling recursive function
    return n * factorial(n - 1);
  }

  public static void main(String[] args) {
    System.out.println("Factorial of the number 5 is: " + factorial(5));
  }
}

Output

Factorial of the number 5 is: 120

Time and Space Complexity

Due to the recursive function being called N times, the time complexity of the aforementioned code is O(N). Because the recursion stack occupies O(N) space in the internal memory, the space complexity of the aforementioned code is once more O(N).

The function call takes up space at the top of the call stack as soon as the recursive function is called. The function calling itself repeatedly takes up space in the call stack by stacking its calls behind them. The graphic below helps us comprehend the call stack.

Factorial() returns 1 when it is called with an argument of 0, after which all other methods return the necessary values and are removed from the call stack.

Iterative Method to Find the Factorial of the Number in Java

In the iterative method:

• Declare the variable res, and set its initial value to 1.
• Run for a loop now, going from 1 to N. Multiply the res variable by the loop counter each time we execute the loop.
• The outcome of the loop execution will then be saved in the res variable.

Code Implementation Find the Factorial of the Number using Loops in Java

class LinearFactorialMethod {

  public static void main(String[] args) {
    int res = 1, N = 10;
    for (int i = 1; i <= N; i++) {
      res *= i;
    }
    System.out.println("Factorial of the number 10 is: " + res);
  }
}

Output

Factorial of the number 10 is: 3628800

Comparing Linear and Recursive Methods

Based on time and space complexity, let’s distinguish between the recursive and iterative methods.
Iterative and recursive procedures both require O(N) time, according to a comparison of their time complexity.

Difference lies in the Space Complexity

The iterative technique uses O(1) constant space for space complexity, whereas the recursive method uses O(N) memory space. This results from O(N) recursive method calls that fill up order N space in the call stack.

Summary

• Recursion divides a problem into smaller ones and identifies the answers to each of these. The larger problem’s solution is constructed from the answers to these smaller ones.
• Where we need to determine the factorial of the number N, the time and space complexity of the recursive technique are both equal to O(N).
• The iterative technique has O(N) and O(1) time and spatial complexity, respectively.
• Recursion requires more space to calculate factorial than the linear technique does. It becomes impossible to compute N! using the recursive technique as N increases in size.
• Recursive code implementation is helpful in many situations when the linear approach fails, including Depth First Search, Breadth-First Search, and Tree Traversal approach.

FAQ related to Find the Factorial of the Number using Recursion in Java

Q1. What is the factorial of 6 by recursion?
Ans. The factorial of 6 is denoted as 6! = 12345*6 = 720

Q2. Is the factorial of 0 equal to the factorial of 1?
Ans. This still counts as a way of arranging it, so by definition, a zero factorial is equal to one, just as 1! is equal to one because there is only a single possible arrangement of this data set.

Q3. Is factorial only for positive numbers?
Ans. The factorial function is a special type of function that multiplies a number by every number below it and gives its product as the output. The factorial function mainly takes only positive integers as well as zero as the domain.