## Java, J2EE & SOA Certification Training

- 32k Enrolled Learners
- Weekend
- Live Class

C Programming and Data Structures (46 Blogs)

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-

- Factorial Program in C using For loop
- Factorial Program using Functions
- Factorial Program using Recursion

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.

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.

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.

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).

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.*