# 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```