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.