# Factorial

Recursion Algorithm

Share

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;
}
``````
Share