Basically , there are four types of **Recursion** in data structure.

But according to our syllabus we have to read only three types i.e. Direct Recursion, Indirect Recursion and Tail Recursion.

## Direct Recursion:

- In direct recursion, a function directly calls itself.
- Each recursive call creates a new instance of the function, which remains active until the base case is reached.
- The base case is a condition that terminates the recursion by providing a result without further recursive calls.

Here’s a Java code example demonstrating direct recursion to calculate the factorial of a number:

```
public class DirectRecursionExample {
public static void main(String[] args) {
int number = 5;
int factorial = calculateFactorial(number);
System.out.println("Factorial of " + number + " is: " + factorial);
}
public static int calculateFactorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * calculateFactorial(n - 1);
}
}
}
```

## Merits of Direct Recursion:

**Simplicity :**Direct recursion often provides a straightforward and intuitive solution for problems that exhibit self-similar subproblems.**Readability :**Recursive functions can often express the problem-solving logic more clearly and concisely, making the code easier to understand.

## Demerits of Direct Recursion:

**Memory Usage :**Recursive function calls consume memory as each call creates a new stack frame. If the recursion depth is large, it may lead to stack overflow errors.**Performance Overhead :**Recursive calls involve function call overhead, which can impact performance compared to iterative approaches.

## Indirect Recursion:

- In indirect recursion, there is a circular dependency among multiple functions, where each function calls another function in a sequence until the base case is reached.
- The recursion ends when the base case is met, at which point the process stops.
- It is designed to support the
*is*even function and should not be called independently for accurate results.

**Here’s an example of indirect recursion in Java where two functions call each other in a circular manner:**

```
public class IndirectRecursionExample {
public static void main(String[] args) {
int n = 5;
System.out.println("isEven(" + n + ") is " + isEven(n));
}
public static boolean isEven(int n) {
if (n == 0)
return true;
else
return isOdd(n - 1);
}
public static boolean isOdd(int n) {
if (n == 0)
return false;
else
return isEven(n - 1);
}
}
```

## Merits of Indirect Recursion

**Problem Decomposition**: Indirect recursion can be useful for breaking down a complex problem into smaller, interdependent subproblems. Each function focuses on solving a specific part of the problem.**Code Modularity**: By dividing the problem-solving logic across multiple functions, the code can be organized and modularized, improving readability and maintainability.

## Demerits of Indirect Recursion

**Execution Order**: The execution order of functions in indirect recursion is crucial. Incorrect sequencing or missing base cases can lead to infinite loops or incorrect results.**Performance Overhead**: Similar to direct recursion, indirect recursion can incur function call overhead and memory consumption. Care must be taken to avoid excessive recursive calls.

## Tail Recursion

- When a recursive function calling itself and that recursive call is the last statement in the function then itâ€™s known as Tail Recursion.
- Also when it call the recursive function performs nothing. The function has to process or perform any operation at the time of calling and it does nothing at returning time.
- Some compilers and interpreters can optimize tail-recursive functions into iterative form, reducing memory usage.

**Here’s an example of a tail-recursive function in Java that calculates the factorial of a number:**

```
public class TailRecursionExample {
public static int factorial(int n) {
return factorialHelper(n, 1);
}
private static int factorialHelper(int n, int result) {
if (n == 0) {
return result;
} else {
return factorialHelper(n - 1, n * result);
}
}
public static void main(String[] args) {
int n = 5;
int factorialResult = factorial(n);
System.out.println("Factorial of " + n + " is: " + factorialResult);
}
}
```

## Merits of Tail Recursion

- Tail-recursive functions can be optimized to use a constant amount of memory.
- Tail recursion enables certain optimizations in some programming languages and compilers.

## Demerits of Tail Recursion

- Debugging tail-recursive functions may be more challenging due to the absence of intermediate stack frames.
- Not all programming languages and compilers support tail call optimization.

## Non-Tail Recursion

- Non-tail Recursion does not perform any operation at the time of recursive calling. Instead, all operations are done at the return time.
- A recursive function is said to be tail-recursive if the recursive call is the last thing done in the function before returning.
- A recursive function is said to be non-tail-recursive
**if the recursive call is not the last thing done in the function before returning**.

**Here’s an example of a non-tail-recursive function in Java that calculates the factorial of a number:**

```
public class NonTailRecursionExample {
public static int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
int n = 5;
int factorialResult = factorial(n);
System.out.println("Factorial of " + n + " is: " + factorialResult);
}
}
```

## Difference between Direct and Indirect recursion:

Highlighting the differences between direct and indirect recursion:

Aspect | Direct Recursion | Indirect Recursion |
---|---|---|

Definition | A function directly calls itself. | Two or more functions call each other in a circular chain. |

Call Structure | Function calls itself. | Functions call each other in a loop. |

Example | `java int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); }` | `java void functionA() { functionB(); } void functionB() { functionA(); }` |

Relationship | Single function involved. | Multiple functions involved. |

Dependency | Only depends on itself. | Functions depend on each other. |

Complexity | Generally simpler. | Can be more complex, especially with multiple functions. |

Base Case Handling | Often explicitly checked in the function itself. | Base case handling might be distributed among functions. |

## Difference between tail and Non-tail recursion:

Highlighting the differences between tail and non-tail recursion:

Aspect | Tail Recursion | Non-Tail Recursion |
---|---|---|

Definition | A special case where the recursive call is the last operation | The recursive call is not the last operation |

Last Operation | Recursive call is the final operation before returning | Other operations follow the recursive call |

Optimization | Tail recursion can be optimized into iteration by compilers | Non-tail recursion may not be optimized into iteration |

Memory Usage | Generally consumes less memory due to optimized execution | May consume more memory due to additional stack frames |

Example | `java int factorial(int n, int result) { if (n == 0) return result; else return factorial(n - 1, n * result); }` | `java int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); }` |

Performance | Often more efficient, especially for large recursions | May be less efficient, especially for large recursions |