. . . About Mathematical Induction

Recursive Algorithms often solve problems by the Divide & Conquer paradigm, which involves three stages: divide, conquer and combine.

• Divide the problem into 2 or more smaller subproblems, whose solutions are strongly related to the solution of the original problem.
• Conquer by calling the recursive algorithm on each subproblem.
• Combine together the subproblem solutions to form the solution to the original problem.

As an example of Divide & Conquer, consider Merge Sort. In this sorting algorithm, the list is divided into two “equal" parts, i.e., within size 1 of each other. Next, each part is sorted recursively, the conquer stage. Finally, the two sorted sublists are combined in a Merge operation, which iteratively compares and transfers the minimum of the two lists. The recursion stops when Merge Sort is called on an array of size 1, which is trivially sorted.¹

Read full article from . . . About Mathematical Induction