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))


Download Projects


Download Programs