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