Program To Compute Nth Factorial Using Recursion

The program to compute Nth factorial using recursion calls a function recursively to compute the output. The recursion is the ability of a computing procedure to call itself repeatedly until the problem is solved.

Problem Definition

In simple words, factorial of a given number \Large n is the product of all the numbers up to that number, including the number. The program computes Nth factorial using recursion.

So factorial of \Large 5 is \Large 1 \times 2 \times 3 \times 4 \times 5 = 120.

See the figure below to understand how recursion works. If \Large factorial () is a function then,

Every time factorial function calls itself, it reduces 1 from the parameter of the function until the \Large factorial(1) is reached.

It starts processing or working from \Large factorial(1) to the top – \Large factorial(n) and prints the final results.

Each of the \Large factorial() function executes the expression containing values returned from the lower level \Large factorial() function. This continues until no more values are available to process.

Flowchart – Nth Factorial with Recursion

Program Codes – Factorial with Recursion

/*Program to compute Nth factorial */
#include < stdio.h >
#include < stdlib.h >
int fact (int n)
{
    unsigned int f;
    if ((n == 0) || (n == 1))
        return (n);
    else
        /* Compute factorial by Recursive calls */
        f = n * fact (n - 1); 
        return (f);
}
main ()
{
    int i, n;
    /* Reading the number */
    printf ("Enter the Number :");
    scanf ("%d", & n);
    /* Printing results */
    for (i = 0; i < 30; i++)
    printf ("_");printf ("\n\n");
    printf ("Factorial of Number %d is %d\n", n, fact (n));
    for (i = 0; i < 30; i++)
    printf ("_");printf ("\n\n");
    system ("PAUSE");
    return 0;
}

#include <iostream>
using namespace std;

int fact(int n) {
    if (n == 0 || n == 1)
        return 1;
    return n * fact(n - 1);
}

int main() {
    int n;
    cout << "Enter the Number :";
    cin >> n;

    for (int i = 0; i < 30; i++) cout << "_";
    cout << "\n\n";

    cout << "Factorial of Number " << n << " is " << fact(n) << endl;

    for (int i = 0; i < 30; i++) cout << "_";
    cout << "\n\n";

    return 0;
}

import java.util.Scanner;

class Factorial {
    static int fact(int n) {
        if (n == 0 || n == 1)
            return 1;
        return n * fact(n - 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter the Number :");
        int n = sc.nextInt();

        for (int i = 0; i < 30; i++) System.out.print("_");
        System.out.println("\n");

        System.out.println("Factorial of Number " + n + " is " + fact(n));

        for (int i = 0; i < 30; i++) System.out.print("_");
        System.out.println("\n");

        sc.close();
    }
}

def fact(n):
    if n == 0 or n == 1:
        return 1
    return n * fact(n - 1)

n = int(input("Enter the Number :"))

print("_" * 30)
print()
print(f"Factorial of Number {n} is {fact(n)}")
print("_" * 30)
print()

In the above source code above following expression calls \Large fact(n-1) several times.

f = n * fact(n-1);

The \Large n is the current number multiplied with values returned by function \Large fact(n-1). However, there are no values yet.

The \Large fact(n-1) calls itself and this process continues till \Large 1 reached.

The actual multiplication starts from \Large fact(1) which return a value and process of returning values continues up to \Large fact(n) processing all returned values.

Finally, the result gets stored in \Large f and the program prints the final output to console.

Output

                Enter the Number:5
                _______________________________
                Factorial of Number 5 is 120
                _______________________________