Recursion Algorithm
In this tutorial we will learn to find the factorial of a number using recursion.
In simple terms, when a function calls itself it is called a recursion.
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
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.
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
Fact(n) Begin if n == 0 or 1 then Return 1; else Return n*Call Fact(n-1); endif End
/*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; }