lab10, CISC105, Fall 2007

Overview

This lab provides more practice with C++, especially iteration and recursion!

You may want to review the idea of a "Design Recipe" from the following wiki pages:

• Design Recipes in MATLAB
• Design Recipes in C++

Prerequisites

Before starting this lab:

• You should already be comfortable with the skills from lab09.
• You should have kept up with the lectures on C++.

Step-by-Step Instructions

Step 1: Preparing your lab10 directory, and copying files you will need

Step 1a: Create a new subdirectory for lab10

Create a new subdirectory ~/cisc105/lab10, and make that your working directory.

Step 1b: Copy the files needed for this week's lab

The files for this lab are in the directory /www/htdocs/CIS/105/haggerty/07F/labs/lab10

Step 2: Examining the example programs

As in past weeks, there is nothing to turn in for Step 2

The work you do in step 2 of this lab is only for practice and learning. There is nothing to turn in from this step of the lab.

So you could skip it if you wanted to, and neither your instructor nor your TA would know.

Well, actually that's not entirely true.

We'd know if,

• you missed the exam questions that were based on this part of the lab
• you asked questions about step 3 that you should have already known if you had actually done this step.

So, don't skip this step.

Step 2a:  C++ Structures

We have learned about some simple data types in C++ such as int, char, double and bool. In this section we will look at structures.

Note:  The following was borrowed from: http://ece-www.colorado.edu/~pfefferz/cpp/tutorial/tutorial/tut3-5.html on 11/24/2007

struct model_name {
  type1 element1;
  type2 element2;
  type3 element3;
  .
  .
} object_name;

If the structure definition includes the parameter model_name (optional), that parameter becomes a valid type name equivalent to the structure. For example:

struct products {
  string name;
  float price;
} ;

products apple;
products orange, melon;

Once declared, products has become a new valid type name like the fundamental ones int, char or short and we are able to declare objects (variables) of that type.

The optional field object_name that can go at the end of the structure declaration serves to directly declare objects of the structure type. For example, we can also declare the structure objects apple, orange and melon this way:

struct products {
  string name;
  float price;
} apple, orange, melon;

It is important to clearly differentiate between what is a structure model, and what is a structure object. Using the terms we used with variables, the model is the type, and the object is the variable. We can instantiate many objects (variables) from a single model (type).

Once we have declared our three objects of a determined structure model (apple, orange and melon) we can operate with the fields that form them. To do that we have to use a point (.) inserted between the object name and the field name. For example, we could operate with any of these elements as if they were standard variables of their respective types:

apple.name
apple.price
orange.name
orange.price
melon.name
melon.price

Now look at struct1.cc and examine how a structure works in code.  Make sure you understand how a structure works...  There is nothing to turn in for this step but you may be tested on this in the future!!!  Could you write a structure for a student with the following information: first name, last name, expected graduation year and GPA?  If so, you are ready to move on!

Step 3: Learning about Recursion

The directory lab10 contains several files this week pertaining to recursion. More examples have been—or will be—discussed in lecture.

In this step, we'll review the recursion related files in the lab10 directory. Then, in Step 4, you'll then be assigned the task of writing several recursive functions yourself.

You may need more discussion of recursion in lecture to know how to tackle these problems. If so, raise this issue with your instructor. These problems are appearing in lab at this time so that you will be more inclined to want to hear more about recursion in the next several lectures!

Step3a: mySum1.cc vs. mySum2.cc

As you may know, finding the sum of a vector in MATLAB is easy—we can use the built-in MATLAB function sum():

>> sum([4 3 0 3])

ans =

    10

>> sum([1 1 2 5 1])

ans =

    10

>> sum([3 5 1])    

ans =

     9

>>

However, it is an important programming skill to know how to find the sum of a vector (or an array) without using a built-in function, because many languages, such as C++, do not have such a function.

So here are two examples of such functions. The first, addElements() in mySum1.cc, initializes the result to zero, and then uses a for loop to step through every element in the vector, adding it into the sum found so far. This is a very common approach:

int addElements(int list[], int size)
{
   int result = 0;

   for(int i = 0; i < size; i++)
      result += list[i];

   return result;
}

The second example, mySum3.m, uses an entirely different approach. This approach uses the following reasoning:

The first two cases are trivial to code:

  if ( size  )
    return result;
  elseif ( lower == size-1)
    return list[lower];
  else
... 

But the third case is where we do the really neat trick. We use a kind of mathematical Jiu-Jitsu to turn the problem against itself, and thus emerge victorious against our opponent.

• We note that the sum of a vector is the sum of its first element list[0], plus the sum of the rest of the vector
• And, to find the sum of the rest of the vector, we just call the function again!

else
   result = list[lower] + addElements(list, lower + 1, size);

At first, you may be worried that this could not possibly work.

• Doesn't this create an infinite loop?
• How can you define something in terms of itself?

The trick is that the recursive call—that is the function call to mySum2() inside the definition of mySum2() is on a smaller vector.

And if the vector is getting smaller with each successive recursive call, eventually we hit one of the base cases—the parts of the function that do not use recursion. At that point, the recursive calls don't go any deeper—we bottom out, and the computation starts winding back out, returning the result we are looking for.

Why use recursion when a for loop will do?

Many students—especially those who have been programming with for loops for a long time—may wonder why recursion is useful. There are several reasons:

• For loops (and while loops) have a limited usefulness.
  • They work well for arrays, but break down on more complex structures like trees
  • Trees are the basis of almost all work on making large scale computing fast—for example, databases use recursive tree structure to store their indexes, compilers use recursive tree structures to process MATLAB, Java, C++ and PHP, and web browsers use recursive tree structures to process HTML code
• Even for simple problems such as computing a sum, the for loop code is actually more complex (even if it is fewer lines)
  • The correctness of the recursive version can be broken down into the correctness of the three parts, each of which can be proven correct independently.
  • The correctness of the for loop version requires an argument about a computation that plays out over time.
• To really understand computer science, and programming, you need to have more than one "problem solving approach" in your toolbox.
  • You cannot be a master carpenter if your only tool is a saw
  • You cannot be a master carpenter if your only tool is a hammer
  • You cannot be a master carpenter if your only tool is a screwdriver.

One of the strengths of using recursion is that it is easy to reason about the problem—construct a logical argument—and then translate that argument directly into code. This often results in code that is easy to understand and maintain.

But I heard that recursion is inefficient and takes lots of computer time.

Don't believe everything you hear, or read. It is true that some recursive functions are slower than the corresponding function written using a for loop—but there are also cases where the recursive version is nearly as fast, or even faster, than the for-loop version. Many textbooks contain statements about recursion that are simply not accurate.

Also, efficiency of computer time is not the only thing we need to optimize for. We also need to take into account how easy code is to write, maintain, and debug. It is often the case that programmer time is more expensive than computer time!

By the way, the word for solutions that use a for loop is iteration.

We contrast these two techniques:

• iteration (for loops and while loops that solve a problem by iterating through steps), and
• recursion (functions that call themselves, moving towards one or more base cases)

Step 4: Working with Recursion and Iteration

Now, some exercises to turn in for credit.

For each of these exercises:

• Produce a C++ that solves the problem
• In Step 5, you'll do one big script file called lab10_step5.txt where you list out all the .m files and run all of your tests.

Step 4a: xAppearsInA.cc using iteration  (use code in lab10 directory as a template)

Write a function xAppearsInA(x,a) that uses a for loop (iteration) to solve this problem:  

• Given a array of numbers a, and an integer x, return true if x appears in v, and false if x does not.  

Rules:

• Use a for loop to check each value in the vector.    
• Do not use any built in C++ functions.

Note:  The file xAppearsInA.cc does not separate out the test file from the code and should be used as a template only... Make sure that you hand in separate files for xAppearsInA.cc and testXAppearsInA.cc (see lab09 if you are unsure how to do this!).

Step 4b: doesXAppearInA.cc using recursion

Write a function doesXAppearInV(x,a) that solves the same problem as Step 4a, but using recursion.  

Again, do not use any built-in C++ functions

Step 4c: myMin.cc using recursion

Write a function myMin(v, lower, size). This is similar to the myMax() function from lab08—but this time, you are finding the minimum element, and doing it using recursion.

Step 4d: countHowMany.cc using iteration

Write a function countHowMany(x, a, size) that counts how many times the number x appears in the array a.  Use a for loop.  

Step 4e: countTheXs.cc using recursion

Write a function countTheXs(x,a,lower,size) that solves the same problem as 4d, but using recursion.  

Step 4f: sevensToNines.cc using recursion

Write a function sevensToNines(a,lower,size) that returns a new vector where all the sevens have been changed to nines.  Use recursion.

To turn in from Step 4

Step 5: Make a diary file lab10_step4.txt.

Now, we want to make a diary file called lab10_step4.txt documenting the work from step 4 of this week's lab.

Put yourself  inside the directory ~/cisc105/lab10, and start a script file called lab10.txt.

Then, for each of the parts of step4 (4a, 4b, etc.)

• cat out the function and test file for that step
• Compile the function file and test file (using the procedure from lab09)
• execute the test file

Step 6: Make a zip file lab10.zip of your .m files

Create a zip file that contains all of your files for this week.

It is ok if the files provided with the lab are included along with the ones you yourself created.

To create and test the zip file, follow the instructions from step11 of lab06 and/or lab07.

The script files may be included directly in the zip file this week.

Step 7: Submit your lab10.zip and lab10.txt file on WebCT

Now you can submit your work on WebCT, and you are done!

Grading: 125 Points TBA

End of lab10 for CISC105, Fall 2007
Due Date: 12/04/2007, 11:55pm
NO LATE SUBMISSIONS ACCEPTED!!!!!