CS16, Summer 2012

Lab07:
C Pointers and Recursion

Goals for this lab

By the time you have completed this lab, you should be able to

Create and use C pointers
Write and test functions that process data via pointers

Step by Step Instructions

Step 1: Get together with your lab partner, and create a lab07 directory

If your assigned partner is more than 5 minutes late, ask the TA to pair you with someone else for this week.

This lab's first pilot should log in, create ~/cs16/lab07/ and make that your current directory.

Step 2: Practice using pointers at the ch prompt

Start ch. Then declare i as int, ip as pointer to int, d as a double array of size 3, and dp as pointer to double. Do not intitialize any of them:

ch> int i, *ip;
ch> double d[3], *dp;

Assign the address of i to ip. Then assign the address of the first element of d (i.e., the name d itself) to dp. And finally, use the ch stackvar command to find out the "state" of your memory area so far (don't worry if your values of ip and dp differ from this example):

ch> ip = &i;
0x9f0f49c
ch> dp = d;
0x9f14770
ch> stackvar
    i                   0
    ip                  0x9f0f49c
    d (C array)
0.0000 0.0000 0.0000
    dp                  0x9f14770

Next set the value of i by using ip, and set the values of d using dp. Type all of the following assignment statements, and then use stackvar to verify i and d are set:

ch> *ip = 17;
17
ch> *dp = 1.25;
1.2500
ch> *(dp+1) = 2.5;  /* notice pointer arithmetic */
2.5000
ch> dp[2] = 3.75;   /* notice pointer used like array name */
3.7500
ch> stackvar
    i                   17
    ip                  0x9f0f49c
    d (C array)
1.2500 2.5000 3.7500
    dp                  0x9f14770

You might be wondering what good are pointers if you already have a variable name you can use more easily. And you are right to wonder about that, because these simple examples are just for instruction, and do not have any programming value in practice. However, there are things we only do with pointers.

Step 3: Fix and test a function to swap two values

First: switch roles between pilot and navigator if you did not already do that.

Get a copy of this useless version of a function that tries to swap two integers: intswap.chf

cp ~kyledewey/cs16/lab07/intswap.chf ~/cs16/lab07/

Read it, and see how it successfully swaps the values stored in a and b: when done, a is set to the value b used to be, and b is set to the old value of a. But then try to use it. Start ch (if necessary), create two integer variables named anything you want (our example uses a and b only to emphasize a point), pass these two variables to intswap, and then type their names to let ch display their resulting values:

ch> int a = 17, b = -4;
ch> intswap(a, b);
ch> a
17
ch> b
-4

Oops. It doesn't work. That's because it processed copies of the variables passed to it, and so it was not able to change the values of the original variables. In C, it is only possible to do that if the function has pointers to these original variables. That means the function must be rewritten to operate on pointers, and it means the addresses of the two variables must be passed to the function. Here are the steps to take and the results to expect:

ch> emacs intswap.chf
ch> remvar intswap
ch> intswap(&a, &b);
ch> a
-4
ch> b
17

Things to notice: (1) ch's remvar command is used to remove the old version of intswap from memory, so ch will load the edited version when it is used - this step means we don't have to exit ch to use the newer version; (2) addresses of a and b are passed to intswap; and (3) it works now!

Open intswap.chf in an editor, and make the following changes:

Type your name(s) in the comment at the top.
Revise the function header so a and b are declared as pointers to int.
Revise the three statements, so a and b are used as the pointers they are now - dereference them to access the memory at which they point. [Thought question: Is there any good reason to treat the temp variable as a pointer too?]

Save the file and exit the editor. Then test the function.

Beware "segmentation faults" that might shut down ch. Read the error messages, and try to fix the problem before asking a TA for help. Also, when you're done with this lab, use rm to delete any files beginning with "core" that might have been created in your current directory.

Step 4: Write a recursive fibonacci number function

First: switch roles between pilot and navigator if you did not already do that.

The Fibonacci sequence is an infinite sequence of integers, one that frequently shows up in mathematics, computer science, and even nature. The first 13 elements of this sequence is shown below (image borrowed from Wikipedia):

Of interest to us is the fact that the sequence is defined using a recursive function with two base cases. It is defined that the first Fibonacci number is 0 (the first base case), and that the second Fibonacci number is 1 (the second base case). This is illustrated below, counting from 0 (image borrowed from Wikipedia):

For all subsequent Fibonacci numbers, it is defined that the nth Fibonacci number is the (n-1)th Fibonacci number plus the (n-2)th Fibonacci number. This is illustrated below (image borrowed from Wikipedia):

For more information on Fibonacci numbers in general, you may wish to consult Wikipedia.

In this portion of the lab, you will write a function that can recursively calculate the value of the nth Fibonacci number. Get a copy of the skeleton code that calculates the nth Fibonacci number from here: fib.chf

cp ~kyledewey/cs16/lab07/fib.chf ~/cs16/lab07/

The provided template contains the code for separating the base cases from the recursive case, but it is missing the actual portion necessary to return values. Add in this code to complete the fib function. The resulting function should behave as follows:

ch> fib(0)
0
ch>fib(1)
1
ch>fib(2)
1
ch>fib(8)
21

Make sure to test your fib code well. You should use the image above showing the first 13 Fibonacci numbers to assist in testing.

Step 5: Get credit for the lab

Don't leave early though ... see challenge problems below. Do the first challenge problem at least, to help you prepare for the final exam. Work on it later if you don't have time during this lab period.

Submit your code with the turnin program. You MUST have both your name and your partner's name in the file in order to receive credit. Remember that the original pilot needs to do this step, since that is whose account you have been using in Cooper Lab.

Bring up a terminal window on CSIL or the Cooper Lab, and cd into the original pilot's cs16 directory, and cd again into the lab07 directory. Then type the following to turn in the function files from Steps 3 and 4 above:
turnin lab07@cs16 intswap.chf fib.chf
Respond "yes" when the program asks if you want to turn in (be sure to read the list of files you are turning in), and then wait for the message indicating success.

Evaluation and Grading

Each student must accomplish the following to earn full credit for this lab:

Turn in a complete and accurate Hw7 - should have done at the beginning of lab.
intswap.chf is saved, and it executes properly with ch.
intswap.chf has been turned in.
fib.chf is saved, and it executes properly with ch.
fib.chf has been turned in.
If a pair completes the above tasks early, they must work the entire lab period by attempting the extra challenge problems below.

Deadline for lab submission: Wednesday 8/15 (11:59pm)

Optional Extra Challenges
Very small revisions to your modified intswap function can make it work to swap pointers. First copy intswap.chf to intptrswap.chf, and edit the new file to make it work as follows (continuing the ch session from Step 3):
ch> int *pa = &a, *pb = &b;
ch> *pa
-4
ch> *pb
17
ch> intptrswap(&pa, &pb);
ch> *pa
17
ch> *pb
-4
ch> a
-4
ch> b
17
As the last two lines show, only the pointers are swapped - now pa points to b, and pb points to a - but the values at a and b are not swapped. Hint: just change all type declarations.
We have already seen an iterative definition of the factorial function, one that gets the product of a series of integers like so (image borrowed from Wikipedia):
However, it is also possible to define a recursive form of the same function, as shown below (image borrowed from Wikipedia):
That is, fac( 0 ) = 1, and fac( n ) = fac( n - 1 ) * n. Write a recursive version of the factorial function, using the above definitions as a guide. The function should take a single int as a parameter and return an int.

Adapted by Kyle Dewey from a lab prepared by Michael Costanzo.