Homework #4
(9 points)

Recursion (recursion recursion recursion...)

Due Date

Section 2: Monday, March 30. Section 1: Tuesday, March 31.

Hardcopy submission, which must be identical to electronic submission, may only be handed in at class on the due date, or directly to your TA. Do not place in folder, except between 3:00 and 5:00 on the due date. Please be careful not to let other people see your solution.

Reading: Chapter 7, and Sections 6.1, 12.2, and 17.1, and pages 631 ("Divide-and-conquer strategies") through 635, first paragraph only -- this will describe merge sort.

Your Mission: Three recursive programming projects, and an extra credit assignment.

In addition to the recursive function that each of these assignments requires you to write, you must test the function by calling it from the main function. For example, to test the quicksort function, write a main function that has the user enter numbers into the array, sorts them, and then prints them out.

  1. Sierpinsky's Triangle

    Write a recursive function to draw Sierpinsky's Triangle, as shown in class. This function will take three sets of coordinates (i.e., six variables of type double) for the corners of the triangle.

    Informally, the algorithm is to:

    However, you also need a base case so it doesn't recurse forever. One way to prevent this behavior is to set a maximum recursion depth. To do so, add as a 7th parameter an integer that decreases by one at each recursive call. The function should check whether this number is too small to do any further recursion.

    If you do not remember what Sierpinsky's triangle looks like from class, run the program ~es66/lib/programs/sirpinsky. This takes a moment to run, but it should refresh your memory.

  2. Palindrome Checker

    A palindrome is a phrase that reads the same forwards and backwards. For example:

    Write a boolean function that answers the question, "Is this string a palindrome?"

    The recursive algorithm is:

    Before calling the palindrome function, there should be a seperate function called to get rid of all the spaces. You don't have to handle punctuation marks.

    Note: Comparing two individual characters can be done with ==.

  3. Quicksort

    Be careful not to confuse this with mergesort, shown in class!

    Here is the pseudo-code algorithm for quick sort. Note that this algorithm cannot handle a list with duplicates (i.e., the same number appearing more than once). You can optionally make a modification to handle this, which would require another base case.

    /* Sort the first n values of List */
    Quicksort(int List[], int n)
        int Small[MAXVALS], Big[MAXVALS];  /* These must be local variables */
                                           /* MAXVALS is a constant         */
        if n is 0 or 1, there is nothing to do (base case)
        else {
            k = random value in List  /*  First pick a random location, then
                                       *  get the value at that location */
            Put all values from List that are smaller than k in a different
    	array, Small.
    	Put all values from List that are greater than or equal to k in a
    	different array, Big.
    	/* Recursively sort the two arrays: */
    	Quicksort(Small, size_of_Small); /* Careful, since size < MAXVALS */
    	Quicksort(Big, size_of_Big);
    	Append Small and Big together into List.  That is, use one or two
    	loops to put the elements of Small into the List array, and then
    	add on the elements of Big.

  4. Recursive Song (optional extra credit)

    Find the values of these recursive functions to produce a three-part number-one pop hit. Embelish with percussion if desired.

    Each value of n is a different eighth-note. There are four measures, so compute the values of base(n), tenor(n) and alto(n) for the first 32 values of n (0 through 31). These four measures repeat forever. It is a really annoying melody that will be stuck in your head for twelve days.

    You can write a program to produce the right values, or you can do it by hand. Below are recursively defined math functions (not C code).

    First, the base and tenor part numbers represent half steps, where 0 is middle C. Therefore, -3 is A and 5 is F. 3 is E flat.

    foundation(0) = 0
    foundation(n) = 5 + foundation(n-1)
    m(n) = foundation(RoundDownToInteger(n/8))
    base(n) = (( m(n) + 6 ) % 12) - 6
    c(0) = 0
    c(n) = 2 + c(n - 1)
    t(n) = c(n) % 6
    tenor(n) = if RoundDownToInteger(n/8) is even, t(n % 8) + base(n)
               else base(n)
    Second, the alto part numbers are not half steps, but rather are positions along a major scale, relative to the value of the base(n) note. This is a major scale starting at the basenote and going up -- the base note is the tonic of the scale, like the key you are in changes according to the base note. By the way, the base note is either 0 or 1 -- I think it is 1 but I forget -- try it both ways to see which sounds better.
    q(0,i,j,x) = x
    q(n,i,j,x) = if (j==0), q(n-1, i+1, i+1, (-1)x)
                 else q(n-1,i,j-1,x)
    arrow(n) = q(n,0,0,-1)
    a(0) = 2
    a(n) = a(n - 1) + arrow(n - 1)
    alto(n) = if RoundDownToInteger(n/8) is odd, a(n % 8)
              else 5

    Show your work. You get one point for producing the sequence of notes, or you can get two points for performing (voice, whistle, or playing a tape of) the correct tune in class on the day it is due.

    Good luck, may the Force be with you, and don't forget to wear ear plugs.


    The deliverables for this assignment are the three programs submitted with email and the three printouts containing the source code for your three programs delivered to your TA.


    Each assignment is worth 3 points.
    1. (1 point) Does the program work and fulfill the requirement of the assignment?
    2. (1 points) Elegance and efficiency of your solution.
    3. (1 points) Formatting, commenting, and decomposition.

    email: evs at cs dot columbia dot edu