Recursion Verses Iteration

Every repetitive problem can be implemented recursively or iteratively Recursion should be used when the problem is recursive in nature. Iteration should be used when the problem is not inherently recursive Recursive solutions incur more execution overhead than their iterative counterparts, but its advantage is that recursive code is very simple. Recursive version of a problem is slower than iterative version since it requires PUSH and POP
operations.

 

In both recursion and iteration, the same block of code is executed repeatedly, but in recursion repetition occurs when a function calls itself and in iteration repetition occurs when the block of code is finished or a continue statement is encountered. For complex problems iterative algorithms are difficult to implement but it is easier to solve recursively. Recursion can be removed by using iterative version.

 

Tail Recursion
A recursive call is said to be tail recursive if the corresponding recursive call is the last statement to be executed inside the function.

 

Example: Look at the following recursive function

void show(int a)
{
if(a==1)
return;
printf(“%d”,a);
show(a-1);
}

 

In the above example since the recursive call is the last statement in the function so the above recursive call is Tail recursive call.

 

In non void functions(return type of the function is other than void) , if the recursive call appears in return statement and the call is not a part of an expression then the call is said to be Tail recursive, otherwise Non Tail recursive. Now look at the following example

 

int hcf(int p, int q)
{
if(q==0)
return p;
else
return(hcf(q,p%q)); /*Tail recursive call*/
}
int factorial(int a)
{
if(a==0)
return 1;
else
return(a*factorial(a-1)); /*Not a Tail recursive call*/
}

 

In the above example in hcf() the recursive call is not a part of expression (i.e. the call is the expression in the return statement) in the call so the recursive call is Tail recursive. But in factorial() the recursive call is part of expression in the return statement(a*recursive call) , so the recursive call in factorial() is not a Tail excursive call.

 

A function is said to be Tail recursive if all the recursive calls in the function are tail recursive. Tail recursive functions are easy to write using loops, In tail recursive functions, the last work that a function does is a recursive call, so no operation is left pending after the recursive call returns. Therefore in tail recursive functions , there is nothing to be done in unwinding phase, so we can jump directly from the last recursive call to the place where recursive function was first called.

 

Tail recursion can be efficiently implemented by compilers so we always will try to make our recursive functions tail recursive whenever possible. Functions which are not tail recursive are called augmentive recursive functions and these types of functions have to finish the pending work after the recursive call finishes.

 

Indirect and Direct Recursion
If a function fun1() calls another function fun2() and the function fun2() in turn calls function fun1(), then this type of recursion is said to be indirect recursion, because the function fun1() is calling itself indirectly.

 

fun1( )
{
……………………… /* Some statements*/
fun2();
……………………… /* Some statements*/
}
fun2( )
{
……………………… /* Some statements*/
fun1();
……………………… /* Some statements*/
}

 

The chain of functions in indirect recursion may involve any number of functions.For example suppose n number of functions are present starting from f1() to fn() and they are involved as following: f1() calls f2(), f2() calls f3(), f3() calls f4() and so on with fn() calls f1(). If a function calls itself directly i.e. function fun1() is called inside its own function body, then that recursion is called as direct recursion.
For example look at the following

fun1()
{
… /* Some statements*/
fun2();
… /* Some statements*/
}

Indirect recursion is complex, so it is rarely used.

 

Try Now – Programming In C MCQs