Recursive algorithm will form a recursive structure in calculation, so it can be proved to be correct by structural induction.
Seeing this name, we will naturally think of mathematical induction.
In fact, it is the generalization of mathematical induction, which means that mathematical induction is its specialization.
It is used to prove that a recursive structure X (list or tree) satisfies the proposition P (x), and the proof method is similar to the familiar mathematical induction.
Firstly, a proposition P (x) is put forward, and it is proved that both the minimum structure and substructure satisfy the proposition P (x), then this recursive structure satisfies the proposition P (x).
This proposition can be used to prove the correctness of the corresponding algorithm after being proved by structural induction.
As in the last article, we use Merge sort as an example, but this time we use its recursive function.
Friends who know merge sorting will know that it adopts divide-and-conquer method.
The central idea of divide-and-conquer method is to recursively divide the problem into sub-problems until the smallest sub-problem (basic situation) can no longer be divided. The solution of the smallest subproblem is simple and clear. At this time, recursively return and merge the answers of sub-questions layer by layer, and finally get the answer of the original question.
The three steps of merge sorting are as follows:
Assuming that the original array is [5 2 4 7 1 3 2 6], it presents the following binary tree structure in the segmentation stage.
First put forward a proposition
Then prove by structural induction:
Therefore, when the height of the binary tree is the maximum, it has been recursively divided into the lowest level (the array size is 1, which can not be subdivided), and the recursion is stopped, and the answers to the sub-questions are merged and returned layer by layer through the merge function, which has been proved to be correct in the last article, so the correctness of the merge sorting algorithm is proved.