Recursion

Recursion is one of the interesting topic. The problems, which can be implemented using loops, can be implemented with Recursion as well. But, most of us go with the looping solution. Today, I am going to set some light on how the same logic can be implemented using recursion. If we could derive a mathematical function for these type of problems, the implementation will be more easier. Lets understand it through some examples.

Example 1 : Factorial 
The factorial of a non-negative number is the multiplication of all the positive integers which are less than or equal to the number.

Suppose fact(n) is a function of n, where x is non-negative integer value. Hence 

fact(0) = fact(1) = 1
fact(2) = 2 * fact(1) = 2
fact(3) = 3 * fact(2) = 6
...
...
... 
fact(n) = n * fact(n-1)

So, the logic would be - If the value of n is 0 or 1 return 1, else return multiplication of n and value of function for (n-1).

int fact(int num) {
    if(num == 0 || num == 1)
        return 1;
    else
        return num * fact (num - 1);
}

Example 2 : Fibonacci Series 

The Fibonacci series is a sequence of integers whose first and second terms are 0 and 1 respectively and  each subsequent term is the sum of the previous two terms. Like - 0, 1, 1, 2, 3, 5, 8, 13, 21, .....

Suppose fibo(n) is a function of n which returns the term n of the fibonacci series and where n > 0 -

fibo(1) = 0

fibo(2) = 1

fibo(3) = fibo(1) + fibo(2) = 1

fibo(4) = fibo(2) + fibo(3) = 2

fibo(5) = fibo(3) + fibo(4) = 3

...

...

...

fibo(n) = fibo(n-2) + fibo(n-1)

So, the logic would be - If the value of n is 1 or 2 return (n-1), else return the addition of value of function for (n-2) and function for (n-1) .

int fibo(int num) {
    if(num == 1 || num == 2)
        return (num - 1);
    else
        return fibo(num - 2) + fibo(num - 1);
}