💡Do you Know what is Recursion in Data Structure?

Introduction to Recursion:

Recursion is a property of defining itself or its type. In programming, while writing a program code when a function calls itself by following some base condition then it is considered a recursion. The function which calls itself is called a recursive function.

For example —

function a()
print(“Example of Recursion”);
a()

Recursion can be defined on the basis of the following characteristics

a) Based on functions call itself 

• • Direct recursion
  • Indirect recursion

b) Based on pending operation at each recursive call

• • Tail Recursive
  • Head Recursive

c) Based on the structure of the function calling pattern

• • Linear
  • Tree

Based on functions call itself

Recursion on the basis of function call itself, it may be called directly or indirectly. Or in other words recursion are of two types:

1. 1. Direct recursion
   2. Indirect recursion

Direct recursion:

If a function calls itself directly within the same function, then it is direct recursion. In this outer function calls the inner function.

fun()  
{  
// write program code  
fun();  
// program code  
}  

Indirect recursion : 

When a function call is done by following transitive property, then such recursion is called an Indirect recursion. Transitive properties say

funA() ➡️funB(),

funB() ➡️funC(),

funC() ➡️funA().

Structure of the indirect recursion

Based on pending operation at each recursive call

• Tail Recursive
• Head Recursive

Tail Recursion :

Tail recursion is a concept in which a function calls itself when all sets of operations were executed before calling that function. It can be correlated with the concept of do while loop. Where do statement will execute first and then while loop will perform. Similar to that, firstly all the statements in the function will execute, and then at last recursive function will execute. In simple terms, A recursive function is called the tail-recursive if the function makes a recursive calling itself, and that recursive call executes last.

do {   // the body of the loop } while (testExpression);

void fun(int n) {     if(n==0)         return 0;     printf(“%d”, n);      fun(n-1); }

Head Recursion

Head recursion is a concept similar to tail recursion, but the only difference is that in this first recursive function call will work then other sets of statements will get executed. No statement or operation will get executed before that function call.

void fun(int n) {
    if(n==0)
        return 0;
    fun(n-1);
    printf(“%d”, n); // Post recursive operation
}

 

Based on the structure of the function calling pattern

• • Linear recursion
  • Binary recursion
  • Tree recursion

Linear Recursion:

When a function calls itself only once then such recursive functions are called linear recursion.

int factorial(int n)

{

if (n==1)

return 1;//base case, as we know that factorial of 1 is 1

else

return n*factorial(n-1);//recursive case

}

Binary Recursion:

When a function calls two recursive calls for every nonbase case then it is called binary recursion. Fibonacci numbers series is best example of binary recursion.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

The Fibonacci sequence is usually defined as follows:

fib(1) = fib(2) = 1

fib(n) = fib(n-1)+fib(n-2),if n>2

There are two base cases. The recursive step calls fib function twice.

function fib(n)

{

if( n <= 2 ) return 1;

else return fib(n-1)+fib(n-2);

}

Tree Recursion:

When a function calls itself more than one time then such recursive functions are called tree recursion.