# Factorial Program in C++

Problem Description

We have to write a C++ program to find out the factorial of a given number with and without using recursion.

What is Factorial Number?

In mathematics, the factorial of a positive integer “n” (represented as “n!”) is the product of all positive integers less than or equal to “n”. The factorial can be calculated using the formula: n! = n x (n-1) x (n-2) x (n-3) … x 1.

For example,
5! = 5 * 4 * 3 * 2 * 1 = 120
The value of 0! is 1, according to the convention for an empty product.

NOTE: Factorial is calculated only for non negative integers.

Problem Solution

There are multiple approaches to calculate the factorial of a number in C++. Let’s explore different methods to find the factorial.

Method 1: (using For Loop)

In this method, we calculate the factorial of a given number using a for loop.

Program/Source Code

Here is source code of the C++ program which computes the factorial of a given number. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```/*
* C++ program to compute factorial of a given integer
*/

#include<iostream>
using namespace std;

int main()
{
int fac;
long long val = 1;

cin >> fac;
cout << endl;
for (int i = 2; i <= fac; i++)
val = val * i;
cout << "The factorial of " << fac << " is " << val << endl;

return 0;
}```
Program Explanation

1. The code calculates the factorial of a number entered by the user.
2. The user is prompted to enter a number, which is stored in the fac variable using cin.
3. A long long variable val is initialized to 1 to hold the factorial value.
4. A for loop starts from 2 and iterates up to the entered number.
5. Inside the loop, val is multiplied by each number, gradually computing the factorial.
6. Once the loop ends, the calculated factorial value is displayed using cout.
7. The code assumes that the entered number is a non-negative integer.
8. This code efficiently computes the factorial of any positive integer entered by the user.

Time Complexity: O(n)
The time complexity of the code is O(n) as it uses a for loop to iterate from 2 to the given number.

Note: Join free Sanfoundry classes at Telegram or Youtube

Space Complexity: O(1)
The space complexity is O(1), as the code uses a fixed amount of space to store variables, regardless of the input size.

Runtime Test Cases

Here is the runtime output of a C program to find the factorial of a number when the number entered by the user is “10”.

```Enter the integer : 10
The factorial of 10 is 3628800```

Method 2: (Using While Loop)

In this method, we calculate the factorial of a given number using a while loop.

Program/Source Code

Here is source code of the C++ program which computes the factorial of a given number using while loop. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```/*
* C++ program to compute factorial of a given integer
*/

#include<iostream>
using namespace std;

int main()
{
int n;
cout << "Enter a positive integer: ";
cin >> n;

int factorial = 1;
int i = 1;
while (i <= n)
{
factorial *= i;
i++;
}

cout << "The factorial of " << n << " is " << factorial << endl;
return 0;
}```
Program Explanation

1. The program prompts the user to enter a positive integer using cout and stores it in the variable n using cin.
2. Variables factorial and i are initialized to 1. factorial will hold the calculated factorial value, and i will be used for iteration.
3. The while loop runs as long as i is less than or equal to n.
4. Inside the loop, the value of factorial is multiplied by i, and the result is stored back in factorial.
5. After each iteration, the value of i is incremented by 1 using i++.
6. Once the loop ends, the program displays the factorial of the entered number using cout.

Time complexity: O(n)
The time complexity of this program is O(n), where n is the value entered by the user.

Space complexity: O(1)
The space complexity is O(1), as the program uses a fixed amount of memory to store variables, regardless of the input size.

Runtime Test Cases
```Enter a positive integer: 5
The factorial of 5 is 120```

Method 3: Factorial using Recursion in C++

In this method, the factorial of a number can be calculated either by creating a separate function or by calculating it directly within the main function.

Expected Input and Output

Case 1. When we take a positive integer

```If the input number is 5,
then the expected output will be 120.```

Case 2. When the number is zero.

```If the input number is 0,
then the expected output will be 1.```
Problem Solution

1. In order to find factorial of a number we can either create a separate function or calculate in the main function itself.
2. First of all input the number whose factorial is to be determined (say n).
3. If the number is 0 or 1 simply return 1.
4. If the number is other than 0 or 1 (say n), then recursively call factorial function as: n*factorial(n-1), where factorial() is the function which returns the factorial of a number.
5. This way we calculate n! as n*(n-1)*(n-2)*(n-3)……..1

Program/Source Code

Here is source code of the C++ Program to find the factorial of a number using recursion. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

1. `/*`
2. ` * C++ Program to find factorial of a number using recursion.`
3. ` */`
4. `#include<iostream>`
5. `using namespace std;`
6. `class fact`
7. `{`
8. `public:`
9. `    /*`
10. `     * Function to find the factorial`
11. `     */`
12. `    int factorial(int n)`
13. `    {`
14. `        int pro = 1;`
15. `        if(n == 0 || n == 1)`
16. `        {`
17. `            return 1;`
18. `        }`
19. `        return n * factorial(n-1);`
20. `    }`
21. `};`
22. `/*`
23. ` * Main function`
24. ` */`
25. `int main()`
26. `{`
27. `    fact f;`
28. `    int n;`
29. `    cout<<"Enter the number whose factorial is to be calculated:\t";`
30. `    cin>>n;`
31. `    cout<<"\nFactorial of "<<n<<" is = "<<f.factorial(n);`
32. `    return 0;`
33. `}`
Program Explanation

1. Here in this program we have created a function called factorial which takes in the number whose factorial is to be determined.
2. We will recursively call the function factorial till n keeps on decreasing to become 1.
3. Since at every recursion we are passing factorial(n-1) after some time this n-1 will become equivalent to 1 which can lead to a terminating case where if n is either 0 or 1, we return 1.
So this way we calculate factorial recursively as n * factorial(n – 1).

Time complexity: O(n)
The time complexity of the factorial function in the code is O(n), where n is the input number. It utilizes recursive calls to calculate the factorial.

Space complexity: O(n)
The space complexity is O(n) due to the recursive calls. Each recursive call adds a new stack frame, consuming additional memory. The space required grows proportionally with the input number.

Runtime Test Cases

Testcase 1: Here is the runtime output of a C program to find the factorial of a number when the number entered by the user is “5”.

```Enter the number whose factorial is to be calculated:    5

Factorial of 5 is = 120```

Testcase 2: Here is the runtime output of a C program to find the factorial of a number when the number entered by the user is “0”.

```Enter the number whose factorial is to be calculated:    0

Factorial of 0 is = 1```

To practice programs on every topic in C++, please visit “Programming Examples in C++”, “Data Structures in C++” and “Algorithms in C++”.