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 n^{th} 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))