Types of recursions in C with examples

Recursion is technique that breaks a problem into one or more sub parts  that are similar to the original problem. A recursive function can be categorized based on

1. Weather the function calls it's self  or indirectly
2. Weather any operation is pending at each recursive call
3. The structure of the calling.

1. Direct recursion

A function said to be direct recursive if it calls explicitly.

Example:

int fact(int n)

{

if(n==1)

return n;

else

return(n*fact(n-1));

}

2. Indirect recursion

A function is said to be indirectly recursive if it contains a call to another function which ultimately calls itself.

Example:

int fun1(int n)

{

if(n==1)

return n;

else

return fun2();

}

int fun2(int x)

{

return fun1(x-1);

}

In the above example the function fun1() calling the fun2() which intern calls the fun1() function.

3. Tail recursion

A recursive function is said to be tail recursive if no operations are pending to be performed. When the recursive function returns to it's caller.

Example:

int fact(int n)

{

if(n==1)

return n;

else

return(n*fact(n-1));

4. Linear recursion

A recursive function is said to be linear recursive when the pending operations does not make another recursive call to the function.

5. Tree recursion 

A recursive function is said to be tree recursive when the pending operation makes another call to the function.