The University of Western Australia
School of Computer Science and Software Engineering
 
 

School of Computer Science and Software Engineering

CITS4406 Problem Solving and Programming

Labsheet 7: Recursion

This is the last labsheet of the semester and you have until the end of May to complete it. Although the lab is not assessed, you must complete it as it reinforces concepts from the lectures especially regarding the divide and conquer problem solving technique and recursion. The labsheet is in two parts: some review exercises from the text ; and an important problem-solving technique, motivated by its use in solving a larger-sized problem representative of the types of problems that can be solved with computers.

Review Exercises (Zelle Chapter 13)

  1. Write a recursive version of the factorial function that takes a natural number n and returns the product of the numbers 1 .. n.
  2. Write a recursive version of the gcd function (that you wrote in your project-1) that takes two natural numbers m, n and returns the largest number that divides without remainder into both m and n.
  3. Write a recursive version of Newton's square root approximation algorithm (see here). (Note that the recursive version will have to take an extra argument which holds the current approximation.)
  4. It might annoy the user to have to provide the initial approximation when they call your recursive function in the previous question. What is the simplest way to overcome this?
  5. Write a recursive function that takes a list of numbers and returns True iff the list is sorted in ascending order, i.e. iff every item on the list is at least as big as the next number.
  6. chilli Given a number x and an ordered list of numbers xs, the fastest way to determine whether x occurs in xs is binary search. Inspect the number y that sits at the mid-point of xs: if x == y, then return True; if x < y, then because xs is ordered, x cannot occur in the top half of the list, so continue the search in the bottom half; if x > y, similarly continue the search in the top half. Write two versions of binary search: one that uses a loop, and one that uses recursion.


Problem Solving Technique: Divide and Conquer


Divide and conquer is the name for a problem-solving technique whereby a problem is solved by splitting (dividing) it into two or more smaller sub-problems of the same type, solving (conquering) each of the sub-problems, then combining these solutions to derive a solution to the original problem.

A simple example from real life is delivering mail to a county containing (say) 100 towns: the problem can be divided into four sub-problems by splitting the mail into geographical regions (north, south, east, west), then solving each sub-problem by delivering the mail within that region.

Divide and conquer is a naturally-recursive technique: if the west region above still contained 60 towns, then we might apply the same technique again to divide that region still further. So the overall solution would look like this:

def deliverMail(towns):
        if len(towns) < threshhold:
                visit each relevant house
        else:
                regions = divide towns into four lists
                map(deliverMail, regions)

Thus a divide-and-conquer solution to a problem has four components:

  • a way of testing whether a problem instance is small enough to solve directly, or (conversely) large enough to justify sub-dividing;
  • a way of generating solutions to small problems directly;
  • a way of dividing a large problem into sub-problems;
  • a way of combining the solutions to the sub-problems into the solution for the original problem.

PROBLEM SOLVING QUESTION 7.1) One of the fastest comparison-based sorting algorithms is mergesort. A long list is sorted by splitting it into two at its mid-poiint, sorting the two halves separately, then merging them back together - which is easy because the two halves are now in order. This is clearly a divide-and-conquer algorithm: the problem of sorting a big list is split into two sub-problems of the same type, then those solutions are combined.

You can implement mergesort by writing two recursive functions.

  • Write a function merge that takes two sorted lists and returns a sorted list containing all of the elements from the two arguments, e.g. merge([2,4,7,8], [1,5,9]) = [1,2,4,5,7,8,9]. (Hint: in order to determine which is the next element on the result, you need only compare the first elements of the two arguments.)
  • Write a function mergesort that takes a list and sorts its elements in ascending order. If the argument has one element or fewer, it doesn't need sorting: if the argument is longer, split it at its mid-point, sort the halves recursively, then merge the sorted halves.

PROBLEM SOLVING QUESTION 7.2) Another fast comparison-based sorting algorithm is quicksort. Given a list xs with more than one element, take the first element of xs (known as the pivot), then partition the other elements of xs into two sub-lists, the first containing all of the elements which are less than the pivot, the second containing all of the other elements, e.g. partition([3,8,1,2,9,7], 5) = ([3,1,2], [8,9,7]). The sorting is completed by sorting these two lists separately, then simply appending the two results together, because we know that the smaller values are on the first sub-list.

quicksort is clearly also a divide-and-conquer algorithm. In fact it is the converse of mergesort: it still works by splitting the list into two, sorting the pieces, then re-combining them, but it applies its comparisons during the splitting process, rather than during the combining process.

You can implement quicksort by writing two recursive functions.

  • Write a function partition that takes a list xs and a value pivot and returns two lists, the first containing the elements of xs that are less than pivot, the second containing the other elements of xs. (Note that partition doesn't do any sorting itself.)
  • Write a function quicksort that takes a list and sorts its elements in ascending order. If the argument has one element or fewer, it doesn't need sorting: if the argument is longer, partition it around the pivot, sort the halves recursively, then join the sorted halves.

School of Computer Science and Software Engineering

This Page

Last updated:
Thu Dec 8 17:51:13 2011

Website Feedback:
[email protected]

https://undergraduate.csse.uwa.edu.au/units/CITS4406/