Lab Quacks

Assignment Description

In this lab you will learn to apply recursive thinking and use the stack and queue data structures. You might also practice templates.

Recursion

What is recursion? Remember CPSC 110? 😀

Recursion is a way of thinking about problems that allows the computer to do more of the heavy lifting for us. It is analogous to the mathematical definition of functions, where you can define a function call in terms of other function calls and basic arithmetic operations, but not in terms of loops.

Why recursion? Being able to think recursively can be tricky, but it is also incredibly powerful. In fact, there are whole languages that entirely use recursion instead of loops, which leads to some very useful optimizations a compiler can make when dealing with such code. There are probably more problems in computer science that are simpler recursively than they are iteratively (using loops). Also, once you have a recursive algorithm, it is always possible to transform it into an iterative algorithm using a stack and a while loop. In this way, computer scientists can think about problems recursively, then use that recursive solution to make an iterative algorithm that may sometimes have lower constant coefficients on time/memory use. (But in the grand scheme of big-O notation, using recursion in most languages has little overhead compared to the rest of the running time.)

How do I write recursively? Recursion just means calling a function within that function’s body. Let’s take an iterative function to calculate the factorial of a number n, n!:

int factorial(int n)
{
    int result = 1;
    for (int i = 1; i <= n; i++)
        result = result * i;
    return result;
}

Okay, so four lines of code. Pretty short and understandable. Now let’s look at a recursive version:

int factorial(int n)
{
    if (n == 0) return 1;
    return (factorial(n-1) * n);
}

Only two lines of code! (Depending on whether you like putting your return statement on the same line.) Even on such a small problem, recursion helps us express ourselves more concisely. This definition also fits better with the mathematical definition:

n! = {

• 1 if n=0
• n*(n-1)! if n > 0

}

A typical recursive function call consists of three parts. Let’s examine the function more closely to see them. Here’s the same code again, with more discussion.

int factorial(int n)
{
    if (n == 0)    // Here is our base case.
        return 1;  // The base case is the smallest problem we can think of,
                   // one we know the answer to. This is the "n = 0" case in
                   // the mathematical definition.

    // optional 'else' here

    return (factorial(n-1) // This is our recursive step. Here we are solving a
                           //   smaller version of the same problem. We have to
                           //   make a leap of faith here - trust that our
                           //   solution to the (n-1) case is correct.  This is
                           //   the same as the mathematical definition, where
                           //   to figure out n!, we need to first figure out
                           //   (n-1)!
               * n         // Here is our incremental step. We are transforming
                           //   our solution to the smaller problem into the
                           //   solution to our larger problem. This is the
                           //   same * n from the mathematical definition.
           );
}

Checking out the code

You can get the files for this lab by downloading lab_quacks.zip.

You can compile your code by typing make and then execute your test cases by typing ./quackfun.

Recursive Exercises

Sum of Digits

Given a non-negative int n, return the sum of its digits recursively (no loops). Note that modulo (%) by 10 yields the rightmost digit (126 % 10 == 6), while divide (/) by 10 removes the rightmost digit (126 / 10 == 12).

int sumDigits(int n);

sumDigits(126) -> 1 + 2 + 6 -> 9
sumDigits(49)  -> 4 + 9     -> 13
sumDigits(12)  -> 1 + 2     -> 3

Triangle

We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on:

*           
* *             
* * *          
* * * *

Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.

int triangle(int rows);

triangle(0) -> 0
triangle(1) -> 1
triangle(2) -> 3

The sum Function

Write a function called sum that takes one stack by reference, and returns the sum of all the elements in the stack, leaving the original stack in the same state (unchanged). You may modify the stack, as long as you restore it to its original values. You may use only two local variables of type T in your function. Note that this function is templatized on the stack’s type, so stacks of objects overloading the addition operator (operator+) can be summed. Hint: think recursively!

template <typename T>
T QuackFun::sum(stack<T> & s);

Non Recursive Exercise

The scramble Function

Your task is to write a function called scramble that takes one argument: a reference to a std::queue.

template <typename T>
void QuackFun::scramble(queue<T> & q);

You may use whatever local variables you need. The function should reverse the order of SOME of the elements in the queue, and maintain the order of others, according to the following pattern:

• The first element stays on the front of the queue.
• Then the next two elements are reversed.
• Then the next three elements are placed on the queue in their original order.
• Then the next four elements are reversed.
• Then the next five elements are place on the queue in their original order.
• etc.

Hint: You’ll want to make a local stack variable.

For example, given the following queue,

front                                         back
0   1 2   3 4 5   6 7 8 9   10 11 12 13 14   15 16

we get the following result:

front                                         back
0   2 1   3 4 5   9 8 7 6   10 11 12 13 14   16 15

Any “leftover” numbers should be handled as if their block was complete. (See the way 15 and 16 were treated in our example above.)

Testing Your Work

The given main.cpp file contains several basic test cases (the same ones we’ll deploy on PrairieLearn). Compile your code by typing make and then execute the test cases by typing ./quackfun.

Marking Your Work

You will let us know you’ve worked on the lab by submitting your work to the autograder in PrarieLearn . We will run a very few simple test cases on your code, and if you pass any of them, you will get credit for the programming portion of the lab. (It’s a low bar.)

Submitting the lab is as simple as dragging your completed code into the PrarieLearn interface for the lab_quack assignment.

Please submit the following files:

• quackfun.cpp
• quackfun.h
• exercises.cpp
• exercises.h

Good luck!

(Optional) The verifySame function

Write the recursive function verifySame whose function prototype is below. The function should return true if the parameter stack and queue contain only elements of exactly the same values in exactly the same order, and false otherwise (see example below). You may assume the stack and queue contain the same number of items!

We’re going to constrain your solution so as to make you think hard about solving it elegantly:

• Your function may not use any loops;
• In your function you may only declare ONE local boolean variable to use in your return statement, and you may only declare TWO local variables of parametrized type T to use however you wish. No other local variables can be used; and
• After execution of verifySame, the stack and queue must be unchanged. Be sure to comment your code VERY well.

Stack
+---+
| 1 | top
+---+
| 2 |              Queue
+---+      +---+---+---+---+---+
| 3 |      | 1 | 2 | 3 | 4 | 5 |
+---+      +---+---+---+---+---+
| 4 |      back            front
+---+
| 5 | bottom
+---+