Types of Recursion in Data Structure

Recursion:

It means the process of solving a problem by reducing it to smaller versions of itself. Recursion is a technique that allows us to break down a problem into one or more sub-problems that are similar in form of the original problem. It is a method for solving those problems which fall into the divide-and-conquer paradigm. In Data Structure, There are two types of recursion:

Types of Recursion:

i. Direct Recursion: In direct recursion, the functions are called themselves. This process involves a single-step recursive call by the function from inside itself.

ii. Indirect Recursion: Where the functions call other functions to call the original function that says Indirect Recursion. This process consists of two steps when creating a recursive call, then it makes functions call functions to make a recursive call. Indirect recursion is also known as Mutual recursion.

Linear Recursion:

Linear recursion can be defined as follows:
i. It performs a single recursive call. If there are more than one recursive calls in a procedure then only one of them should be chosen based on some tests or criteria.
ii. Define each recursive call, so that it makes progress to the base case.

Binary Recursion:

Binary recursion can be defined as follows:
i. It performs two recursive calls for each non-base case.
ii. It defines each recursive call so that it makes progress to the base case.

Multiple Recursion

: Multiple recursion can be defined as follows:
i. It performs many recursive calls.
ii. Define each recursive call, so that it makes progress to the base case.

Example:
Suppose a problem has the following recursive definition:

F(x)= c for F(x)
= F(H(x)) for other values of x.

For the above problem condition, 1 is the base case and condition 2 implies a recursive call. So for x = G(x) return the value c to the calling function and for the other values of r call the same function with the new argument H(x).

 

Algorithm fnF(x)
{
if(x==G(x))
return c;
else
fnF(h(x));
} // End of Algorithm