HHLL: Problems 1 Answers

The code for the answers is also in wwll_answers1.cpp.

1. Implement a function countUp that uses recursion to count up from 0 to a given number. For example, countUp(3) is the list (0 1 2 3) and countUp(2) is the list (0 1 2). If the given number is less than 0, countUp should return NULL, the empty list. For example, countUp(-1000) is the empty list. Hint: Have countUp call a recursive function that takes a second parameter -- a variable to hold the current count.

//Post: Returns a list containing the numbers from 0 up to
//and including the given number. Return the empty list
//if the 0 > number.
Node* countUp(int number)
{
    return countUp(number, 0);
}

//Post: Returns a list containing the numbers from count up to
//and including number. Returns the empty list
//if count > number.
Node* countUp(int number, int count)
{
    if (count > number) {
        return NULL;
    }
    else {
        return createNode(count, countUp(number, count + 1));
    }
}

2. Implement a recursive function collectMatches that copies only the elements of a list that equal a given value. For example, if x is the list (2 1 3 2), collectMatches(x, 2) is the list (2 2) and collectMatches(x, 1) is the list (1). If no elements match, return the empty list, NULL. For example, collectMatches(x, 5) is the empty list.

//Pre: head is a valid linked list.
//Post: Returns a list of all the values in head
//equal to value.
Node* collectMatches(Node* head, int value)
{
    if (head == NULL) {
        return NULL;
    }
    else if (head->data == value) {
        return createNode(value, collectMatches(head->link, value));
    }
    else {
        return collectMatches(head->link, value);
    }
}

3. Implement a function readList that uses recursion to read a list in the format we've described from a given istream. For example, if you call readList(cin) and the user enters "(1 2)" your function should return the list (1 2). If the user enters "()", readList() should return the empty list, NULL. Hint: Have readList read just the opening parenthesis, '('. Implement a recursive function to do the rest of the work.

//Pre: in is not errored and has a valid list description
//ready to be read.
//Post: Returns the list corresponding to that that was on in.
Node* readList(istream& in)
{
    char left;
    in >> left;
    return readRestOfList(in);
}

//Pre: in is not errored.
//Post: Any leading spaces on in have been read.
void skipSpaces(istream& in)
{
    while (isspace(in.peek())) {
        in.get();
    }
}

//Pre: in is not errored and contains the portion
//of a list description following the opening parenthesis.
//Post: Returns the list corresponding to what
//remains on in.
Node* readRestOfList(istream& in)
{
    skipSpaces(in);
    if (in.peek() == ')') {
        return NULL;
    }
    else {
        int next;
        in >> next;
        return createNode(next, readRestOfList(in));
    }
}