Week 8 Slog

Hi,everyone!

After doing so much recursive exercise, I think I am supposed to have a better understanding of recursive function. But in this week's lab's lab, my partner and me were still struggle for how to build a recursive.

We just covered how to prove the correctness of a recursive algorithm in our CSC 240 class. Basically, every correct recursive algorithm can be proved by strong induction. I think considering the base case is extremely essential for writing a recursive function. Also, we can use strong induction to help us to write it.

Taking an example we used in CSC 240, let's say, we want to write a recursive algorithm that Sort a list. By strong induction, we have the algorithm does what we want for len=1,2,3,4,5...n-1. Now if we want sort a list with length n, then we can just divide the list into 2 parts and do the recursion. Then, by MergeSort, we put 2 parts together and it is still correct which follows by strong induction.