Sunday, September 4, 2011

How to work with 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);
}
I hope, this post will really helpful.

9 comments:

  1. But whenever a recursive call is made current set of storage is pushed into stack and another copy of storage vars is created for the next call . So be diligient while making such calls. As if when there is long chain of recursive call eventually would result in to stack out of memory.

    ReplyDelete
  2. Thanks for the comment. Definitely need to take care on that front as well.

    ReplyDelete
  3. Nice article. Tx.
    Just to add, for recursion work efficiently, we should make our function re-entrant.

    ReplyDelete
  4. can you please provide some thing about threading and multi-threading.

    ReplyDelete
  5. These two examples are good to understand recursion, but this implementation is very inefficient. The iterative implementation of factorial and fibonacci are much faster.

    ReplyDelete
  6. yes definitely, but I think that these could be the simplest implementation to understand the recursion

    ReplyDelete
  7. Wow, that was quick!! Khatarnak response time hai ;)

    ReplyDelete