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:
Example:boolean even_check(int n){if(n==0)return true;elsereturn odd_check(abs(n)1);}Boolean odd_check(int n){if(n==0)return false;elsereturn 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.
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
E.g.: n! = n * (n1)!
long int fact(int n)
{
if(n==0)
return 1;
return (n*fact(n1)); // 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.
If a functions only first statement holds a recursive call then it is called tail recursion. E.g.:
E.g: Refer to previous odd and even functions.
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
E.g.: n! = n * (n1)!
long int fact(int n)
{
if(n==0)
return 1;
return (n*fact(n1)); // 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(n1, 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 counterpart 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 nonrecursive procedure/functions.
 If proper precautions are not taken, recursion may result in nonterminating 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 
Also you can Join our Facebook Group : Programmer 2 Programmers
0 comments:
Post a Comment