Saturday, 4 January 2014

Saturday, January 04, 2014
Recursion
The concept of recursion may prove daunting some times. But don't we are here to help you out on this. In this tutorial we will provide you with an idea of the different forms of recursion with examples for better understanding. 

So what is a Recursion?

Recursion is a method where the answer to the problem depends on solutions to smaller cases of the same problem. So here we discuss about some unusual recursions as follows.

Indirect Recursion (Special Case)


Mutual Recursion:

Mutual Recursion
Mutual Recursion

Example:
boolean even_check(int n)
{
    if(n==0)
        return true;
    else
        return odd_check(abs(n)-1);
}
Boolean odd_check(int n)
{
    if(n==0)
        return false;
    else
        return even_check(abs(n)-1);
}
// we want to check that whether a given number (n) is even or not.

Mutual recursion is a form of recursion where two mathematical or computational functions are defined in terms of each other. That means, say, first function is f() and second function is g() then the pictorial view of mutual recursion is as follows :

E.g: Refer to previous odd and even functions.

recursion

Tail Recursion: 


If a functions last statement only holds a recursive call then it is called tail recursion.
Example:
f()
{
    ……………
    ……………
    g();
    ……………
    ……………
    f();
}
g()
{
    ……………
    ……………
    return #;
}
// Recursive call at last statement
tail recursion

E.g.:  n! = n * (n-1)!
long int fact(int n)
{
    if(n==0)
        return 1;
    return (n*fact(n-1));    // R * f(n)
}

Whether R * f(n) happens then it is not the last statement of the function factorial then we can say it is not a tail recursion.

factorial(n)
{
    return factorial1(n,1);
}
factorial1(n,f)
{
    if(n==0)
        return  f;
    return factorial1(n-1, n*f);
}
factorial1(n,f)    // Not a tail recursion but a perfect working copy of
{    //  previous program ( factorial ).
    while(n!=0)
    {
        f*=n;
        n-=1;
    }
    return f;
}

Head Recursion: 


If a functions only first statement holds a recursive call then it is called tail recursion. E.g.:
void reverse(char *s)
{
    if(*s != ‘\0’ )
    {
        reverse(s+2);
        printf(“%c”,*s);
    }
}


Recursion Vs Iteration:




Iteration
Recursion
It is a process of executing a statement on a set of statement repeatedly until some specific condition is specified.
Recursion is the technique of defining anything in terms of itself.
Iteration involves 4 clear cut steps like initialization, condition, execution and updating (inc/dec).
There must be an exclusive if statement inside the recursive functions, specifying stopping condition.
Any recursive problem can be solved iteratively.
Not all problems have recursive solution.
Iterative counter-part of a problem is more efficient in terms of memory utilization and execution speed.
Recursion is generally a worst option to go for simple problems, or problems not recursive in nature.
In Iteration we used variable to store result.
In Recursion we used stack to store result.


Disadvantages of Recursion:

  • It consumes more storage space because the recursive calls along with automatic variables are stored on the stack.The computer may run out of memory, if recursive calls not checked.
  • It not more efficient in terms of speed and execution time.
  • According to some computer professional recursion doesn’t offer any concrete advantage over non-recursive procedure/functions.
  • If proper precautions are not taken, recursion may result in non-terminating iteration.
  • Recursion is not advocated when the problem can be through iteration. Recursion may be treated as a software tool to be applied carefully and selectively.

Contributors: 


Author Editor
If you like this tutorial then do share it along and also subscribe to our Website RSS Feeds for more such amazing tutorials.

Also you can Join our Facebook Group : Programmer 2 Programmers

0 comments:

Post a Comment