C Programming and Data Structures (41 Blogs)

Factorial Program in C: How to calculate factorial of a number?

Published on Jul 10,2019 799 Views
Aayushi Johari
A technophile who likes writing about different technologies and spreading knowledge. A technophile who likes writing about different technologies and spreading knowledge.

MI-new-launch

myMock Interview Service for Real Tech Jobs

myMock-mobile-banner-bg

myMock Interview Service for Real Tech Jobs

  • Mock interview in latest tech domains i.e JAVA, AI, DEVOPS,etc
  • Get interviewed by leading tech experts
  • Real time assessment report and video recording

Factorial of a positive integer is the product of an integer and all the integers below it, i.e., the factorial of number n (represented by n!) would be given by

             n! = 1*2*3*4* . . . . . *n

The factorial of 0 is defined to be 1 and is not defined for negative integers. There are multiple ways to find it which are listed below-

Let’s get started.

Factorial Using For Loop

It is the easiest and simplest way to find the factorial of a number. Let us first visit the code –

#include <stdio.h>

 int main()

{

    int I , num , fact = 1; //defining factorial as 1 since least value is 1

   printf (“Enter a number to calculate its factorial”);

   scanf (“%d”, &num);

   if (num<0) //if the input is a negative integer

   {

   printf (“Factorial is not defined for negative numbers.”);

   }

   else

   {

   for(i=1;i<= num;i++) //for loop doesn’t gets executed for input 0 as 1>0,  therefore fact value remains 1

{

fact = fact * i;  // keeps on multiplying and storing in the value of factorial till the input integer is reached

              }

   printf(“Factorial of %d = %dn”, num, fact);

    }

    return 0; //since we have defined the main() method with a return value of integer type

}

Output-

 Factorial of 5 = 120

Explanation

The number whose factorial is to be found is taken as input and stored in a variable and is checked if it is negative or not. If the integer entered is negative then appropriate message is displayed. The value of factorial is predefined to be 1 as its least value is 1. The for loop is executed for positive integers (except for 0 for which test condition is false and thus fact remains zero). In the for loop, the value of factorial is multiplied with each integer and stored successively till the input number is reached. For example, for input = 5, the flow goes to for loop and following steps take place-

fact =1,i=1 –> fact= 1*1=1 –> i=2
fact =1,i=2 –> fact= 1*2=2 –> i=3
fact =2,i=3 –> fact= 2*3=6 –> i=4
fact =6,i=4 –> fact= 6*4=24 –> i=5
fact =24,i=5 –> fact= 24*5=120 –> i=6

Now 6>5, therefore test condition becomes false and the loop is terminated. The value of factorial is displayed.

Factorial Using Functions

This approach is known as a modular approach and should be followed for programming as it is quite efficient. One of its advantages is that when we need to make changes to code then instead of changing the complete code, we can just modify the function concerned. The code for finding the factorial of a number using this approach is shown below

#include <stdio.h>
 
long factorial(int num)     //function for calculating factorial which takes an integer value as a parameter and returns an int type value
{
  int i;
  long fact = 1;
 
  for (i = 1; i <= num; i++)
	fact = fact * i;
 return fact;   	//returns to function call
}
 
int main()        	//execution begins from main() method
{
  int num;
 
  printf("Enter a number to calculate its factorialn");
  scanf("%d", &num);
  if(num<0) //if the input is a negative integer
  {
   printf("Factorial is not defined for negative numbers.");
   }
  printf("Factorial of %d = %dn", num, factorial(num));                             	//call to factorial function passing  the input as parameter
   return 0;
}

 

Output – Factorial of 5 = 120

Explanation-

The logic for the program is the same except that different function is used to calculate the factorial and return the value to the main method from where the execution begins.

Factorial Using Recursion

Recursion is the process in which a function calls itself and the corresponding function is called recursive function. It consists of two parts- a base condition and a recursive call. The solution to the base condition is provided while the solution to the larger value can be solved by converting to smaller values till the base solution is reached and used. 

Below is the code for finding factorial using recursion:-

#include<stdio.h>
int fact(int);     //function prototype
int main()
{
    int num;
    printf("Enter the number whose factorial is to be find :");
    scanf("%d" ,&num);
    if(num<0)
    {
        printf("ERROR. Factorial is not defined for negative integers");
    }
    printf("Factorial of %d is %d", num, fact(num));  //first call is made
    return 0;
}
int fact(int num)
{
    if(num==0)    //base condition
    {
        return 1;
    }
    else{
        return(num*fact(num-1));   //recursive call
    }
}

Output – Factorial of 5 = 120

Explanation– Suppose the user enters 5 as input, then in main() method the value of num is 5. As the flow goes in the printf statement(line 12) a call to fact(5) function is made. Now for fact(5) num is 5 which is not equal to 0, therefore flow goes to the else statement where in return statement a recursive call is made and fact(4) is made. The process is repeated till the base condition, i.e., num=0 is reached and 1 is returned. Now flow goes to fact(1) from where 1(as for fact(1) num=1)*1(value returned from fact(0)) is returned. This process is repeated until the required value is obtained. 

Time & Space Complexity – Recursion V/S iteration

For Recursion-

Regarding time complexity, we know that factorial 0 is the only comparison. Therefore T (0) =1. For factorial of any other number the process involves one comparison, one multiplication, one subtraction, and one function call. Therefore 

T (n) =T (n-1) +3
= T(n-2)+6
= T(n-3)+9
= ….
= T(n-k)+3k

Since we know T (0) =1 and for k=n, (n-k) =0

Therefore T (n) =T (0) +3n
= 1+3n

Therefore time complexity of the code is O (n).

Regarding space complexity, a stack is created for each call which will be maintained until its value is computed and returned. For example for n=5 the following stacks will have to be maintained 

f (5) -> f (4) -> f (3) -> f (2) -> f (1) ->f (0)

As we can see that 5 stacks will have to be maintained until a call to f(0) is reached whose value is known and is returned. Therefore for n factorial, n stacks will have to be maintained. Thus space complexity is O(n). It is also evident from the above pictures that for n=5,  5 stacks will have to be maintained. Therefore for n factorial, n stacks will have to be maintained. Thus space complexity is O(n).

For Iteration-

Regarding time complexity, there are n iterations inside the loop, therefore the time complexity is O(n).

Regarding space complexity, for iterative solution there is only one stack that needs to be maintained and an integer variable is used. So the space complexity is O(1).

That’s all for this article. I hope you have understood the concept of the factorial program in C along with the time complexities.

If you come across any questions, feel free to ask all your questions in the comments section of “factorial program in C” and our team will be glad to answer.

Comments
0 Comments

Browse Categories

webinar REGISTER FOR FREE WEBINAR
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP

Subscribe to our Newsletter, and get personalized recommendations.