## Recursive Function

Recursive function can be defined as a function calling itself. When a function is called from the same function then it is known as recursion.
There are lots of problem that can be solved using concept of recursive function. Following are some of the problems that can be solved using recursive function:
(1) Factorial Number
(2) Greatest Common Divisor
(3) Fibonacci Series

## Factorial Number

Factorial of the Number can be calculated using following equation:
n! = n * (n-1)!

 1, if n = 1 FACT (n) = n * FACT (n-1), otherwise

Example:
5! = 5 * (5-1)!
= 5 * 4!
= 5 * 4 * (4-1)!
= 5 * 4 * 3!
= 5 * 4 * 3 * (3-1)!
= 5 * 4 * 3 * 2!
= 5 * 4 * 3 * 2 * (2-1)!
= 5 * 4 * 3 * 2 * 1!
= 5 * 4 * 3 * 2 * 1
= 120

Algorithm:
If N=1 then
Return 1
Return (N * FACT (N-1))

## Greatest Common Divisor

Greatest Common Divisor of two integer number is the largest integer number that divides both the numbers.
Greatest Common Divisor can be calculated using following recursive equation:

 n, if n divides m GCD (m, n) = GCD (n, m mod n), otherwise

Example:
GCD (62, 8) = 62 % 8 = 6
= GCD (8, 6)
= 8 % 6 = 2
= GCD (6, 2)
= 6 % 2 = 0
Thus, GCD (62, 8) = 2

Algorithm:
Step 1: REMINDER = (M mod N)
Step 2: If REMINDER = 0 then
Return N
Else
Return (GCD (N, REMINDER))

## Fibonacci Series

Fibonacci Series can be given as:
0 1 1 2 3 5 8 13 21 34 ….
In above Fibonacci Series first two terms are fixed 0 and 1. Third term of series can be calculated as a sum of first and second terms. Similarly fourth term can be calculated as a sum of second and third term and so on.
We can find nth term of Fibonacci series using following recursive function:

 0, if n = 0 or 1 FIBO (n) = 1, if n = 2 FIBO (n-1) + FIBO (n-2), if n > 2

Example:
FIBO (5) = FIBO (4) + FIBO (3)
= FIBO (3) + FIBO (2) + FIBO (2) + FIBO (1)
= FIBO (2) + FIBO (1) + 1 + 1 + 0
= 1 + 0 + 1 + 1 + 0
= 2 + 1
= 3

Algorithm:
If N=0 or N=1 then
Return 0
Else if N=2 then
Return 1
Else
Return (FIBO (N-2) + FIBO (N-2))