ISC Practicals and Theory - Factorial

The factorial of a non-negative whole number is the product of all whole numbers from 1 up to that number. This note finds it using a recursive method, that is, a method that calls itself on a smaller number until it reaches a number whose factorial is known.

Definition

The factorial of a number $n$, written $n!$, is the product of all positive integers from 1 to $n$. By definition $0! = 1$.

$n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$

For example:

• $4! = 4 \times 3 \times 2 \times 1 = 24$
• $0! = 1$

The same definition can be written in terms of itself: $n! = n \times (n-1)!$ for $n \ge 1$, with $0! = 1$. This is why recursion suits it.

Algorithm

1. Start. In main, create an object ob of class Factorial.
2. Call input(): it accepts the number and stores it in the data member n.
3. Call display():
   • If n is less than 0 or greater than 20, print an error message and stop. A long cannot hold $21!$, so 20 is the largest number allowed.
   • Otherwise call fact(n) and print the result.
4. The recursive method long fact(int x) works like this:
   • Base case: if x is 0 or 1, return 1.
   • Recursive case: return x * fact(x - 1).
   • Each call waits for the smaller call to return, then multiplies.
5. Stop.

Program

The constructor sets n to 0, input() reads the number, fact(int x) calls itself to find the factorial, and display() checks the range and prints the answer.

import java.util.Scanner;

public class Factorial
{
    int n;

    Factorial()
    {
        n = 0;
    }

    void input()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number (0 to 20): ");
        n = sc.nextInt();
    }

    long fact(int x)
    {
        if (x <= 1)
            return 1;
        return x * fact(x - 1);
    }

    void display()
    {
        if (n < 0 || n > 20)
            System.out.println("Invalid input. Enter a number from 0 to 20.");
        else
            System.out.println("Factorial of " + n + " = " + fact(n));
    }

    public static void main(String args[])
    {
        Factorial ob = new Factorial();
        ob.input();
        ob.display();
    }
}

Variable description table

Sample input and output

Enter a number (0 to 20): 5
Factorial of 5 = 120

Enter a number (0 to 20): 0
Factorial of 0 = 1

Enter a number (0 to 20): -3
Invalid input. Enter a number from 0 to 20.

Dry run

Input: n = 5. The calls go down until the base case, then the values come back up.

Coming back: fact(2) returns $2 \times 1 = 2$, fact(3) returns $3 \times 2 = 6$, fact(4) returns $4 \times 6 = 24$ and fact(5) returns $5 \times 24 = 120$. The output is Factorial of 5 = 120, the same as the real run above.

Variations

1. Strong number "A number is a strong number if the sum of the factorials of its digits equals the number. Write a program to check it, using a method to find the factorial."
2. Sum of digit factorials "Accept a number and display the sum of the factorials of its digits."
3. Combinations "Write a program to find nCr, using a method that returns the factorial of a number."