Factorial

In this tutorial we will learn to find the factorial of a number using recursion.

What is recursion?

In simple terms, when a function calls itself it is called a recursion.

Factorial of n

Factorial of any number n is denoted as n! and is equal to
n! = 1 x 2 x 3 x ... x (n – 2) x (n – 1) x n

Factorial of 3

3! = 1 x 2 x 3
   = 6

Factorial Function using recursion

F(n)  = 1       when n = 0 or 1
      = F(n-1)  when n > 1

So, if the value of n is either 0 or 1 then the factorial returned is 1.

If the value of n is greater than 1 then we call the function with (n - 1) value.

Example

Find 3!

We know,

F(n) = 1           when n = 0 or 1
     = n x F(n-1)  when n > 1

So,
F(3) = 3 x F(3-1)
     = 3 x F(2)

and F(2) = 2 x F(2-1)
         = 2 x F(1)

We know, F(1) = 1

Therefore,
F(2) = 2 x F(1)
     = 2 x 1
     = 2

Similarly,
F(3) = 3 x F(2)
     = 3 x 2
     = 6

Factorial Pseudo Code

Fact(n)
Begin
  if n == 0 or 1 then
    Return 1;
  else
    Return n*Call Fact(n-1);
  endif
End

Factorial code in C

/*factorial declaration
recursive and non-recursive
*/

#include <stdio.h>

//function declaration
int fact(int n);
int nonRecFact(int n);

int main(){
  //variable declaration
  int n, f;
  
  //input
  printf("Enter n:  ");
  scanf("%d", &n);
  
  //recursive fact
  f = fact(n);
  printf("Recursive fact: %d\n", f);
  
  //non-recursive fact
  f = nonRecFact(n);
  printf("Non-Recursive fact: %d\n", f);
  
  return 0;
}

//function definition
int fact(int n){
  if(n == 0 || n == 1)
    return 1;
  else
    return n * fact(n-1);
}

int nonRecFact(int n){
  int i, f = 1;
  for(i = 1; i <= n; i++)
    f *= i;
  return f;
}