Lab 11: Recursion

Assignment

For this assignment you will be doing two things that are related. The first of which is to write a recursive function that will find the minimum element in a list of numbers. The second is to create a function that recursively sorts a list of numbers from least to greatest using the findMin function you created.

findMin(oldList, currentMin) Should first copy oldList into something called myList(see below), then pull out the first element(remove from the list) and compare it with currentMin. If it is less than currentMin, set currentMin to that element. Otherwise, leave currentMin alone.

If there are no more elements in the list(the base case), return currentMin. Otherwise(general case), call the findMin function again, passing in myList and currentMin, and return that value. The general case return should look like this:

return findMin(myList, currentMin)

myList = list(oldList)

To practice good programing, you should check to see how long the list is first before you do anything because you cannot find the first element of an empty list. If the list is empty, return currentMin

The second part of this lab is to write a sorting function that used our findMin function. We will name this function sort(jumbledList, sortedList).

Let's think. A list sorted from least to greatest has the least element first, and the greatest element last. And what can we easily do to lists in some sort of order? Append! We can keep appending elements to a list without caring about what other elements are in the list and be guaranteed that what we just added is at the end of the list. This will be important for us. If we have a jumbled list and find and remove the minimum element in it, and then append that to an empty list (lets call it newList), we know that newList is sorted from least to greatest. Now if we find and remove the minimum element of our jumbled list and append it to newList, we know that newList is still sorted in least to greatest order. See below:

newList = []
jumbledList = [5, 6, 3, 9, 1]
#find and remove min element
#min element is 1
#append it to newList
newList.append(1), #[1]
#now:
jumbledList = [5, 6, 3, 9]

#find and remove min element
#min element is 3
#append it to newList
newList.append(3), #[1, 3]
#now:
jumbledList = [5, 6, 9]

[1, 3, 5, 6, 9]

See if you can use the concepts you used in findMin to write this sorting function.

For main, just copy what is given below exactly, but make sure you understand how I call findMin and sort.

def main():
    jumbledList = [404, 398, 119, 134, 147, 243, 367, 44, 291, 328, 309, 79, 498, 310, 436, 321, 41, 354, 30, 281, 239, 65, 207, 186, 308, 72, 406, 458, 418, 442, 271, 448, 262, 407, 18, 149, 196, 210, 326, 247, 414, 129, 496, 264, 280, 453, 387, 15, 4, 273, 452, 173, 317, 27, 212, 121, 366, 169, 85, 297, 235, 224, 460, 187, 120, 319, 362, 396, 390, 408, 464, 213, 208, 393, 229, 287, 204, 303, 66, 215, 277, 13, 206, 200, 165, 110, 211, 378, 112, 6, 337, 133, 97, 353, 52, 295, 124, 471, 274, 455, 141, 231, 413, 47, 440, 7, 67, 329, 249, 441, 145, 237, 336, 256, 130, 117, 43, 108, 444, 457, 360, 183, 17, 154, 46, 38, 251, 90, 283, 349, 179, 316, 36, 466, 69, 238, 463, 246, 394, 76, 276, 426, 456, 40, 358, 216, 202, 499, 75, 483, 214, 487, 470, 222, 417, 312, 50, 252, 100, 480, 427, 490, 194, 102, 305, 21, 339, 106, 131, 205, 105, 340, 467, 282, 155, 451, 391, 402, 3, 377, 122, 430, 126, 176, 351, 74, 217, 338, 476, 80, 376, 445,  128, 137, 352, 115, 150, 55, 123, 219, 81, 88, 381, 492, 482, 261, 195, 478, 384, 420, 132, 343, 114, 241, 432, 244, 403, 473, 475, 469, 70, 292, 500, 311, 401, 58, 31, 257, 267, 25, 54, 346, 87, 189, 410, 148, 139, 152, 356, 265, 193, 415, 19, 245, 388, 389, 56, 481, 332, 270, 167, 484, 380, 438, 151, 5, 477, 99, 254, 203, 104, 135, 443, 11, 450, 125, 348, 399, 320, 294, 236, 421, 82, 409, 269, 96, 62, 306, 361, 379, 300, 109, 95, 166, 333, 159, 465, 364, 385, 313, 437, 103, 449, 344, 86, 33, 158, 314, 347, 180, 255, 24, 42, 221, 350, 363, 497, 157, 375, 8, 20, 93, 298, 234, 479, 368, 341, 374, 331, 230, 172, 60, 428, 424, 201, 286, 279, 296, 73, 439, 345, 63, 185, 371, 190, 162, 383]

    min = findMin(jumbledList, jumbledList[0])
    print("The first min is %d" % min)
    jumbledList.remove(min)
    min = findMin(jumbledList, jumbledList[0])
    print("The second min is %d" % min)
    #depending on how you return in the sort function, you will have to use either of the following 2 lines:
    sortedList = sort(jumbledList, [])
    #jumbledList, sortedList = sort(jumbledList, [])
    print(sortedList)

main()

Remember that findMin needs something to compare against initially. Rather than hardcode a value that I think will be higher than everything else, I simply give it the first item in my list. I can only do this because I know my list is not empty. If the first element just happens to be the least element in the list, findMin will return it as such. If it is not, then findMin will still find the correct min element.

The reason I give sort an empty list to start is so that sort can just append numbers without having to check if what we gave it is a list or not. It also guarantees that there will not be any extra items in the list that ruin the sortedness of the list.