C Program To Find Factorial Of A Number Using Function

Problem Analysis

Factorial of a number is multiplication of all integers preceding it. To find the factorial of a number multiplication of all natural numbers smaller than it is carried out.

Mathematical notation of factorial of a number say n is –

n! = n * (n-1) * (n-2) * (n-3). . . 3 * 2 * 1

For example, if n is 4 then,

n! = n * (n-1) * (n-2) * (n-3)

4! = 4 * 3 * 2 * 1

As per the mathematical theorem, the factorial of 0 is 1. Fatorial is used in sorting algorithms, quantum physics, in RNA sequences etc.

Size of the result of the factorial of a number increases exponentially. In order to store the result of a factorial, a computer would require approximately about 600 to 800 bits making it impossible for any fixed size data types to overcome the problem of overflow.

Different programming languages have different implementations of integer data types and floating point data types. Programming language communicates with the operating system to execute its programs, so no programming language can support numeric values greater than the number of bits supported by the operating system. In personal computers, the number of bits supported by the operating system is 32-bits or 64-bits. Thus, the largest factorial that can fit in personal computers is 65!.

To find factorial of large absolute values of integers divide-and-conquer technique should be used. Calculating factorial of large absolute values of integers using divide-and-conquer techniques is more efficient than sequential multiplication technique (1 x 2 x 3 x 4 x 5….).

Another method of calculating factorial of a number is prime factorization. By using prime factorization technique code can execute faster but the problem of memory overflow can not be avoided. Run-time complexity of prime factorization techniques is O(logp(N)).

Problem Description

Factorial of a number in C language can be calculated using three methods:

Using for loop.
Using functions
Using Divide-and-Conquer technique

Calculating factorial of a number using for loop.

To calculate factorial using for loop a variable in for loop is initialized to 1 and it is incremented until it becomes equal to the number of which factorial is to be calculated.

Each time a loop is executed, the loop variable is multiplied with flag variables.

Calculating factorial of a number using function.

In this code factorial is calculated using function. Instructions to calculate factorial is put in a separate programming block out of function main ( ). Placing problem logic in a separate block enables programmers to attain flexibility in achieving reusability as function can be called from different programming blocks.

Another objective of using function is to attain robustness. Any change made in function will not affect other programming blocks thus making the program robust.

Calculating factorial using Divide-and-Conquer

Divide-and-Conquer technique uses recursion. In C language recursion is implemented using recursive functions, recursive functions are those functions that call themselves. Recursive functions divide the problem into a finite set of subproblems. This division of problems into subproblems continues till a subproblem is formed that is solved directly.

A recursive function that calculates factorial of a natural number is as follows:

n! = }	1 if n or n =1
	(n-1)! . n for n > 1

As it can be analysed that for n > 1 factorial can be calculated for a number if we already know the factorial of that number less by 1 that is, (n-1). The above definition has terminating conditions defined for n = 0 and n = 1. Terminating condition is for n = 0 or n = 1 and value 1 is returned.

Solution to Problem

Following is the program to calculate the factorial of a number using three methods:

Using for loop
Using function
Using Divide-and-Conquer technique

C Program to calculate factorial using for loop

#include <stdio.h>
int main()
{
  int p, num, f = 1;
 
  printf("Enter a number to calculate its factorial\n");
  scanf("%d", &num);
  for (p = 1; p <= num; p++)
    f = f * p;
 
  printf("Factorial of %d = %d\n", num, f);
 
  return 0;
}

Output:

Input a positive integer number: 5

Required factorial of 5 = 120

Code Analysis

Execution of for loop in this code works like this:

If user input 4 than value of the variable p and f is as follows:

for loop cycle -1:

p = 1
f =1

f = f *p
f =1 * 1

p = 2
f = 1

for loop cycle -2:

p = 2;
f = 1;


f = f * p;
f = 1 * 2;

p = 3;
 f = 2

for loop cycle -3:

p = 3;
f = 2;

f = f * p;
f = 2 * 3;

p = 4;
f = 6

for loop cycle - 4:

p = 4;
f = 6;

f = f * p;
f = 6 * 4;

p = 5;
f = 24

for loop cycle - 5:

The value of p is 5, and 5 is greater than number 4, execution condition of for loop is false thus for loop is terminated. Factorial of the number is displayed on the screen by displaying the value of f.

C Program to Calculate the Factorial of a Number using function

#include <stdio.h>

long f_actorial(int);

int main()
{
  int num;

  printf("Please input positive integer to calculate factorial of a number \n");
  scanf("%d", &num);

  printf("%d! = %ld\n", num, f_actorial(num));

  return 0;
}

long f_actorial(int num)
{
  int p;
  long f = 1;

  for (p = 1; p <= num; p++)
    f = f * p;

  return f;
}

Output:

Please input positive integer to calculate factorial of a number 

4
4! = 24

Code Analysis

Factorial of the number is calculated using the function long f_actorial (int num).
The function has return type long and has an argument of type integer.

Program execution begins with main( ) from where the user defined function long f_actorial(int num) is called. Inside function f_actorial(int num) logic of calculating the factorial of the number is written. When factorial is calculated, the final result is displayed.

Code execution in for loop takes place like this:

If user input 4 than value of the variable p and f is as follows:

for loop cycle -1:

p = 1
f = 1

f = f * p
f = 1 * 1

p = 2
f = 1

for loop cycle -2:

p = 2;
f = 1;

f = f * p;
f = 1 * 2;

p = 3;
f = 2 

for loop cycle -3:

p = 3;
f = 2;

f=f*p;
f=2*3;

p = 4;
f = 6

for loop cycle - 4:

p = 4;
f = 6;

f = f * p;
f = 6 * 4;

p = 5;
f = 24

for loop cycle - 5:

The value of p is 5, and 5 is greater than number 4, execution condition of for loop is false thus for loop is terminated. Factorial of the number is displayed on the screen by displaying the value of f.

C Program to Calculate Factorial of a Number by Divide-and-Conquer Technique using Recursion

#include<stdio.h>
 
long f_actorial(int);
 
int main()
{
  int num;
  long f;
 
  printf("Please input positive integer to find factorial of a number\n");
  scanf("%d", &num);
 
  if (num < 0)
    printf("I can not caluculate factorial of a negative integer.\n");
  else
  {
    f = f_actorial(num);
    printf("%d! = %ld\n", num, f);
  }
 
  return 0;
}
long f_actorial(int num)
{
  if (num == 0) 
    return 1;
  else
    return (num * f_actorial(num-1));
}

Output:

Please input positive integer to find factorial of a number

4
4! = 24

Code Analysis:

This program finds the factorial of a number by Divide-and-Conquer technique using recursion. A recursive user defined function long f_actorial(int num) is used to calculate the factorial of a number.

User input positive number and that number is taken in a user-defined variable num in function main ( ). This is done using the following code:

   printf("Please input positive integer to find factorial of a number\n");
   scanf("%d", &num);

Value of variable num is compared with 0, if it is smaller than 0 then message “I can not calculate factorial of a negative integer.” is displayed to the user. Code for this is:

             if (num < 0)
             printf("I can not calculate factorial of a negative integer.\n");

If the value of num is not smaller than 0, num is passed to the user defined function long f_actorial(int num).

Inside function long f_actorial(int num) value of variable num is ckecked if num is 0 then code within the if block is executed otherwise the code within the else block is executed.

If num is 0, 1 is returned as the factorial of 0 is 1, otherwise, recursive function long f_actorial(int num) is called. This is done by executing the following code:

                                         if (num == 0) 
                                              return 1;
                                        else
                                              return (num * f_actorial(num-1));

Execution cycle is something like this:

num
num*f_actorial(num-1)
5
5 * fact(4)
4
4 * fcat(3)
3
3 * fact(2)
2
2 * fact(1)
1
1 * fact(0)

Return values are: 


Function
Return Value
Result
1 * f_actorial(0)
return 1;
1 * 1 = 1
2 * f_actorial(1) 
1
2 * 1 = 2
3 * f_actorial(2)
2
3 * 2 = 6
4 * f_actorial(3)
6
4 * 6 = 24
5 * f_actorial(4)
24
5 * 24 = 120


At last result 120 is displayed to the user.

Recursion is implemented using stack. Run time complexity of calculating the factorial of a number using recursion is O(n).

Conclusion

C Program to Find Factorial of a Number can be implemented using three methods – first, using for loop, second, using function, and third, by a divide-and-conquer technique using recursion.

All three programs have a run time complexity of O(n). All three programs can calculate factorial upto absolute integer value 65. The difference between the three program is in the implementation technique.

In the first program that is calculating factorial using a for loop, the program control counter does not have to leave the main( ) function. Program logic to calculate the factorial is within the mian( ) function itself leading to fast execution as the operating system does not have to maintain and update address tables.

In the second program that is finding factorial using function logic to calculate factorial of a number is written in a separate block which is outside of the function main(). Since the program control counter has to move to a function which is outside of the function main( ) operating system has to maintain and update address tables accordingly leading to extra CPU clock cycles, making this program less efficient than the first program using a for loop.

Third program to calculate factorial of a number by divide-and-conquer technique using recursion also uses a function, thus it has the same complexity as that of the program to calculate factorial using a function. As recursive calls use stacks this program has an extra overhead of maintaining stack making it even less efficient in terms of memory usage then other two programs.

Factorial of a number is a simple program but its understanding is critical since it has a hidden technique – Divide-and-Conquer.