In class exercises

Create a w10-recursion subdirectory
in your cs21/class directory and copy over my starting point files:

$ cd $ cd cs21/inclass $ pwd /home/your_user_name/cs21/inclass $ mkdir w10-recursion $ cd w10-recursion $ pwd /home/your_user_name/cs21/class/w10-recursion $ cp ~adanner/public/cs21/w10-recursion/* . $ ls mergesort.py recursion.py

- Open recursion.py. We are going to write some iterative and recursive versions of the same function. Iterative versions use loops, recursive versions do not use loops, and instead contain calls to themselves. The idea of recursive functions is based on recursive definitions. For example, n! can be defined as n(n-1)!.
- Next, open mergesort.py. Merge sort is a faster sorting algorithm
than selection sort. It uses the same type of divide and conquer
strategy as binary search does. It is also an example of an
elegant recursive solution.
We are going to look at the mergeSort code together. Once we understand how the recursive calls work, you are going to come up with an algorithm for merging two sorted lists of size n into a sorted list of size 2n. Your merging algorithm should be iterative (not recursive). Once you have an algorithm, try coding it up in the merge function.