Recursion and Divide & Conquer Approach

Using a recursive algorithm, certain problems can be solved quite easily. Key Ideas to understand in recursion

• Different ideas of Recursive solutions
• Correctness and Base Cases
• Stack Overflow Scenario
• Iteration Vs Recursion
• Analysis of recursion using Recursion Tree Method and Master Theorem

Divide-and-Conquer approach : It Breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem. This method usually allows us to reduce the time complexity to a large extent.

• We use a recursive approach during the solution of the problem using Divide and Conquer, Dynamic Programing and Backtracking. We also solve several arrays, tree, linked list, string and graph-related Interview problems using recursion.
• Important Recursive Algorithms: Binary Search, Merge Sort and Quick Sort. There are several commonly asked interview questions that use the idea of binary search.