Find the Factorial of the Number using Recursion in Java

Last Updated on September 4, 2024 by Abhishek Sharma

In computer programming, finding the factorial of a number is a common problem that can be solved using various methods. One of the most elegant and intuitive ways to calculate the factorial is by using recursion. Recursion is a technique where a function calls itself to solve smaller instances of the same problem until a base condition is met. In this article, we will explore how to find the factorial of a number using recursion in Java, providing a clear understanding of both the concept and its implementation.

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.

Conclusion
Calculating the factorial of a number using recursion in Java is a straightforward and efficient approach. Recursion simplifies the problem-solving process by breaking down the factorial calculation into smaller, manageable steps. However, it’s important to ensure that the base condition is correctly defined to prevent infinite recursion and stack overflow errors. Understanding and implementing recursive functions like this one is a fundamental skill for any programmer, as it helps in solving complex problems with elegant solutions.

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

1. What is a factorial, and how is it calculated?
A factorial of a non-negative integer
n is the product of all positive integers less than or equal to n. It is denoted as n!. For example, 5!=5×4×3×2×1=120.

2. What is recursion in programming?
Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem until a base condition is met.

3. How does recursion help in finding the factorial of a number?
Recursion simplifies the factorial calculation by reducing the problem to smaller sub-problems.

4. What are the risks of using recursion?
If not implemented correctly, recursion can lead to infinite loops and stack overflow errors, especially if the base condition is not well-defined or the recursive calls are too deep.

5. Can the factorial of a number be found without using recursion?
Yes, the factorial can also be calculated iteratively using loops, which can be more efficient in terms of memory usage, as it avoids the overhead associated with multiple function calls in recursion.