Calculate factorial of a given number

Posted by on Mar 31, 2024

A number "n" is given, the task is to calculate and print factorial of n using recursion.

Example: Print factorial of 5

Input: 5
Output: 120


Solutions

Method 1: Tail Recursion

Factorial of a given number n is calculated by multiplying the number with all the numbers less than n up-to 1; i.e. fact(5) = 5 * 4 * 3 * 2 * 1. Or we can say fact(5) = 5 * fact (4), fact(4) = 4 * fact(3) and so on.

We can solve this problem using Tail Recursion easily, all we need to do is to pass an extra variable to the function to store the factorial value, i.e. fact(n, accumulator).

package com.cb.recursion;

/**
 * Tail Recursion
 */
public class R4_Factorial {

    public static long factorial(long n, long accumulator) {
        if (n == 1)
            return accumulator;
        return factorial(n - 1, n * accumulator);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5, 1));
        System.out.println(factorial(25, 1));
    }
}
120
7034535277573963776
Complexity

In every fn call, we are increasing start index and decreasing end index, that means fn is called n/2 or n/2+1 times for a string of size n; so Time Complexity is O(n).

We are also storing startIndex and endIndex in every call, so Space Complexity is 2n or O(n).

Method 2: Head Recursion

Factorial of a given number n is calculated by multiplying the number with all the numbers less than n up-to 1; i.e. fact(5) = 5 * 4 * 3 * 2 * 1. Or we can say fact(5) = 5 * fact (4), fact(4) = 4 * fact(3) and so on.

We can solve this problem using Head Recursion easily, all we need to do is, multiply current value of n with the return value of "recursive call to fact (n-1)". The base condition will be to return 1 if n==1.

package com.cb.recursion;

/**
 * Head Recursion
 */
public class R3_Factorial {

    public static long factorial(long n) {
        if (n == 1)
            return 1;
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));
        System.out.println(factorial(25));
    }
}
120
7034535277573963776
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).

Related


Program to solve "Tower of Hanoi" problem

Program for printing nth Fibonacci Number

Sum of the digits of a given number

Write a program to reverse a string

Calculate the Power of a Number (n^p)

Check if an integer array is sorted or not

Print spelling for a given number

Count ways to reach the nth stair

Print numbers from a given number to 0

Print numbers from 0 to a given number