### Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as **recursive function**.

**Base Condition**: In a recursive problem, solution to the base case is provided and solution to bigger problem is expressed in terms of smaller problems.**Stack Overflow**: In a recursion if the base condition is not reached and the function call stack reaches its limit, a stack overflow error is thrown.**Direct vs Indirect Recursion**: A function is**direct recursive**if it calls the same function, but a**indirect recursive**function calls a different method which inturn calls the original function.**Tail Recursion**: If the recursive call is the last thing executed by the function.**Disadvantage**: Greater space requirements and additional overhead for function calls and return values.

### Divide and Conquer Approach

The divide and conquer paradigm involves three steps:

**Divide**: Divide a problem into a number of smaller subproblems.**Conquer**: Solve the subproblems recursively.**Combine**: Combine solution to subproblems to get the solution of original problem.

For example **merge sort** is based on divide and conquer paradigm. It follows the following steps:

- Divide array of size n to be sorted into two of size n/2.
- Sort the sub-arrays recursively.
- Combine the two sorted sub-arrays to get the sorted array.

Base case is when the sub-array has only a single element and is trivially sorted.

Auxiliary procedure Merge(A, p, q, r) where A is the array and p, q and r are indices into the array such that p <= q <= r.

Merge procedure assumes that the sequence A[p .. q] and A[q+1 .. r] are in sorted order and return A[p .. r] in sorted order.

**Time Complexity of the Merge(A, p, q, r) procedure is O(n)**.

## REFERENCES:

Introduction to Algorithms 3rd Edition - Chapter 2

Recursion - GeeksforGeeks