# Recursion Basics & Factorial of a Number Program in C++

# What is Recursion?

Recursion is a technique where a function calls itself again and again until an exit condition is met.

# Where to use Recursion?

Recursion is useful when you have to do a repetitive task where only the input or output values change at every step.

Also, exit condition is crucial when using recursion as it defines when to stop calling the function and prevent an infinite loop.

# Factorial with Recursion

• Factorial is used to compute the number of permutations (combinations) of arranging a set of n numbers.

• Factorial of a number n = n! = 1 * 2 * 3 * …. * n

Examples:

3! = 1 * 2 * 3 = 6

6! = 1 * 2 * 3 * 4 * 5 * 6 = 720

1! = 1

0! = 1 (because an empty set can only be ordered in 1 way)

Now let's try to write a function to calculate the factorial of a number using recursion.

Input for our program

Number for which we have to calculate the factorial i.e. n

Output of our program

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

As we can see we are doing a repetitive task of multiplying numbers from 1 to n, we can use recursion to calculate factorials.

Now the factorial of a number n would be:

n! = 1 * 2 * 3 * …. * (n – 1) * n 

Similarly, factorial of a number (n-1) will be:

(n – 1)! = 1 * 2 * 3 * …. * (n – 1) 

Now combining the above two statements we can say that, factorial of a number n is factorial of (n-1) multiplied by n. Which gives us:

n! = (n – 1)! * n

And we can say that if we have to create a function to calculate factorial of number n it will be equal to:

f(n!) = f(n – 1)! * n

Therefore, we have to write a function which multiples a number n with the factorial of previous number (n – 1) until we reach 1, where 1 is our exit condition and we know that 1! = 1.. Therefore we will break out of the recursive call if n == 1.

Now as we have discussed before that the factorial of 0 is also equals to 1, we also have to handle the case where we directly get the value of n as 0 in our function, for this we will add n == 0 as well in our exit condition.

# Source Code - C++

#include <iostream>
using namespace std;
int factorial(int n) {
  // exit condition
  if (n == 1 || n == 0) {
    return 1;
  } else {
    // recursive function call
    return n * factorial(n - 1);
  }
}
int main() {
  int n, result;
  cout << "Enter a positive integer: ";
  cin >> n;
  result = factorial(n);
  cout << "Factorial is: ” << result;
  return 0;
}