lab09, CISC106, Fall 2007

Special note for Conrad's honors sections only:

On this lab, you may work in pairs.

If you work in pairs,

The words above are specific to this lab.

This does NOT establish a precedent for future labs—unless specifically instructed otherwise, always assume that collaboration at the level of working on code together is not permitted, and may constitute academic dishonesty.

The words above are specific to this lab.

This does NOT establish a precedent for future labs—unless specifically instructed otherwise, always assume that collaboration at the level of working on code together is not permitted, and may constitute academic dishonesty.

Overview

In this lab, we'll briefly return to the Katrina plots in lab05. We'll then explore further the topics of iteration and recursion.

Goals

By the time you complete this lab, you should be able to:

  1. Demonstrate that you can work with plots in MATLAB without detailed directions
  2. Code function M-files to perform simple tasks on vectors using both iteration and recursion

Step-by-Step Instructions

Step 1: Preliminaries

To prepare for this week's lab, do all the following steps. If you are not sure what to do at any stage, you can consult earlier labs for details:

Step 2: Return to Katrina

We promised a return to the Katrina plots...

Back in lab05, the instructions indicated that later in the semester, we'd return to the problem described in lab05—namely, plotting graphs dealing with hurricane Katrina—to make two more plots:

Well, that time has come

And, because you now have much more familiarity with MATLAB than you did four weeks ago, I'm giving you the opportunity—the learning opportunity—to tackle this problem on your own.

Here's what you need to do:

To be graded

Step 3: Learning about Recursion

The directory lab09 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 lab09 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.m vs. mySum2.m

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 do not have such a function.

So here are two examples of such functions. The first, mySum1.m, 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:

  result = 0;
  
  
  for i=1:length(x)
  
    result = x(i) + result;
    
  end % for

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

There are only three possibilities for a vector x:

The first two cases are trivial to code:

  if ( isempty(x)  )
    result = 0;
  elseif ( length(x) == 1)
    result = x;
  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. 

else

    result =  x(1) +  mySum2 (x(2:end))  ;    
end

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

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:

Step3b: testing mySum1() and mySum2()

Your lab09 directory contains test scripts for mySum1.m and mySum2.m, called (not surprisingly) testMySum1.m and testMySum2.m.

Look at the test scripts, and then run them to convince yourself the both of these functions do in fact correctly find the sum of a vector.

Step3c: Another recursive function

We can also use recursion to produce various kinds of output.

We know that printing a vector in MATLAB is as simple as typing the name of the vector without a semicolon. For example, these three lines of MATLAB create a vector x with three elements, add an element to the vector, and finally print out the entire vector:

>> x = [4 5 1];
>> x  = [x 8]; 
>> x

x =

     4     5     1     8

>>

But, some programming languages (including C++, which we will soon be studying) do not have any way to just print out an entire vector or array. To print out an entire array in some languages, we have to use either a loop, or recursion.

Printing a vector with a for loop is left for you as an exercise. Code to do it using recursion is contained in the file printArray.m in this week's lab09 directory. Here is the main part of the body. Notice that there are three cases, as before:

Here is the code that implements this reasoning:

  if ( isempty(x)  )

    fprintf('[]\n');

  elseif (length(x)==1)

    fprintf('%2.0f\n', x(1));

  else

    fprintf('%2.0f ', x(1));
    printArray (x(2:end));

  end

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:

Step 4: Working with Recursion and Iteration

Now, some exercises to turn in for credit.

For each of these exercises:

Step 4a: xAppearsInV.m using iteration

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

Rules:

Step 4b: doesXAppearInV(x,v) using recursion

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

Again, do not use any built-in MATLAB functions other than isempty and length.

Step 4c: myMin.m using recursion

Write a function myMin(v). 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(x,v) using iteration

Write a function countHowMany(x,v) that counts how many times the number x appears in the vector v.  Use a for loop.  Use no built in functions except length and isempty.

Step 4e: countTheXs(x,v) using recursion

Write a function countTheXs(x,v) that solves the same problem as 4d, but using recursion.   Use no built in functions except length and isempty.

Step 4f: sevensToNines(v) using recursion

Write a function sevensToNines(v) that returns a new vector where all the sevens have been changed to nines.  Use recursion. Use no built in functions except length and isempty.

To turn in from Step 4
  function M-file test script M-file technique
Step4a xAppearsInV.m testXAppearsInV.m iteration
Step4b doesXAppearInV.m testDoesXAppearInV.m recursion
Step4c myMin.m testMyMin.m recursion
Step4d countHowMany.m testCountHowMany.m iteration
Step4e countTheXs.m testCountTheXs.m recursion
Step4f sevensToNines.m testSevensToNines.m recursion

Step 5: Make a diary file lab09_step4.txt.

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

Put yourself inside MATLAB, inside the directory ~/cisc106/lab09, and start a diary file called lab09.txt.

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

Step 6: Make a zip file lab09.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 diary files may be included directly in the zip file this week.

Before you submit your lab09.zip file on WebCT (step 7) be sure that your plots from step 2 are readable on the web.

Step 7: Submit your lab09.zip file on WebCT

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

Grading: @@@ Points TBA

 

step what we're looking for points
step@@@

@@@

 @@
overall following of directions student should follow the directions given @@
Total    

 

End of lab09 for CISC106, Fall 2007
Due Date: 11/13/2007, 11:55pm