Factorial

Recursion

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
Example

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

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)

Now, F(1) = 1
Therefore,
F(2) = 2 x F(1) = 2 x 1 = 2
and, 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;
}