Calculate and print factorial of a given number

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

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));
    }
}