Assignment 7 Recursive programming

// ~ Overview ~ //

Recursion is an elegant method for solving many problems. At first it
can seem unnatural; however, it is actually very simple once you are
used to it. The key thing to understand is that recursive programming
has two steps:
(1) A base case which is trivial.
(2) A recursive case where you write the solution for the larger case
in terms of the solution to smaller cases.

What makes (2) easy is that you simply *assume* that you have the
solution of a smaller case. Life does not generally let you assume you
have a solution that you have not yet found; however, if you think
about it, it should be obvious (by induction) that recursion works
this way.

In this assignment, we will use (1) and (2) above to sort linked-lists
of strings using the "merge-sort" algorithm. Merge-sort is a beautiful
algorithm that sorts extremely quickly with large inputs. It is also the
best possible algorithm to use for sorting linked-lists.

Included in the assignment files is a file called "example.c". This
file contains the code for merge-sorting arrays of strings. In this
assignment we will re-implement this code to work with link-lists. The
result will look different; however, the essential idea will be
exactly the same.

Merge sort works as follows:

(1) Base case:
You never need to sort a list of length 0 or 1; it is already
"sorted", so-to-speak. To implement the base case, simply return the
input list if its length is 0 or 1. (In general, base cases are
trivial like this.)

(2) Recursive case:
Lets wave our hand, and assume that we know how to sort smaller lists
already. (See, recursion is easy.) For the recursive case, we do the
following:
(2.a) Divide the list into two smaller lists of equal size, +/- one
node.
(2.b) Recursively sort each of the two smaller lists. (Wow: easy.)
(2.c) You now have two small lists that are sorted. To produce the
final large sorted list, you "merge" the two smaller lists together.
(2.c.i) Create a brand new empty list, which will be the result-list.
(2.c.ii) While both small lists are non-empty, look at the head
node of each. Take the smaller head node off of the front
of its list, and append it to the result-list.
(2.c.iii) Eventually one (or perhaps both) of the smaller lists will
be empty. At this stage, append the non-empty list (if there
is one) onto the end of the result-list.

That is merge sort.

You never need to allocate or copy memory (or create new Nodes) when
merge-sorting linked-lists. It is important that you discover how to
do this. You cannot pass the tester if you allocate or create
list-nodes when sorting. Hints on how to do this are included in the
assignment file "answer07.h".

Note: In general, merge-sorting arrays requires some sort of buffer
that is proportional to the size of the array. It is for this reason
that we use qsort -- quick-sort -- instead of merge-sort. Merge-sort
is always superior with linked-lists.

// ~ Learning Goals ~ //

(1) Recursion
(2) Linked-lists (structures)
(3) Memory management

// ~ Assignment Files ~ //

+ answer07.h: Header file contains the declarations that you must
implement. These functions must be implemented in a file called
"answer07.c".
+ example.c: Some example code that shows merge-sort with arrays of
strings. You can do whatever you want with this file. It will not be
marked. Do not include it in the submission. It is there purely to
provide hints.
+ README: this file.
+ tester: for testing your assignment
+ testcases: a directory that contains code that is used by the
tester. The tester will not run if you edit these files. They are
provided purely for your convenience: You may be interested in what
the tester is doing to test your code.
+ output-tester: When you run the tester, it will save the output of
each testcase and the valgrind log for each testcase in separate files
inside of this directory. Please review these files if you
fail a testcase, so that you can recreate the problem yourself.

// ~ Determining Your Mark ~ //

The tester program is there to ensure that you have followed the
instructions correctly.

Run the tester program as follows:

./tester