COE428 Lab 2: Recursion

COE428 Lab 2: Recursion
Program development and debugging
This is a one week lab. This lab must be submitted at least 48 hours before
the beginning of your next lab period.
Prelab preparation
Before coming to the lab you should:
• Read the lab. Try to prepare any questions you may have about the lab.
• Refer to Lab Guide.
• Create your lab directory for lab2. (i.e. use mkdir lab2 within your coe428
directory.)
• Change to your coe428/lab2 and unzip the lab2.zip file with the command:
 unzip /home/courses/coe428/lab2/lab2.zip

Introduction
This lab reviews even more basic C programming with an emphasis on recursive
algorithms. You will:
• Use programs to aid your understanding of recursion.
Tutorial I: Recursion in C
You have learned in your lectures how to describe and code (in C) several algorithms that
are recursive. We re-examine the classic Towers of Hanoi algorithm here.
Specifications for executable
The specs are:
• Towers are identified with a single integer: the left, middle and right towers are
named as '1', '2' and '3' respectively.
• The program should print (to stdout) the moves required to solve the problem as a
sequence of lines in the format:
 FROM_ID SPACE DEST_ID

For example, to move 3 disks from Tower 1 to Tower 2, the stdout output should be:
1 2
1 3
2 3
1 2
3 1
3 2
1 2

• NOTHING ELSE should be written to stdout.
The algorithm can be expressed in C as:
#include <stdio.h>
#include "towers.h"
void towers(unsigned int n, unsigned int from, unsigned int dest)
{
 unsigned int spare = 6 - from - dest;
 if (n != 0) {
 towers(n-1, from, spare);
 printf("%d %d\n", from, dest);
 towers(n-1, spare, dest);
 }
}

Displaying debugging information
In order to see how the algorithm runs, it is useful to display additional information as the
program runs. For example, more insight might be gained if the output was something like:
towers(3, 1, 2) Initial invocation
..towers(2, 1, 3) Recurse (indentation indicates depth)
....towers(1, 1, 2) Recurse
......towers(0, 1, 3) Recurse (base case, returns immediately)
......Move #1: From Tower 1 to Tower 2 First move (by towers(1, 1, 2)
......towers(0, 3, 2)
....Move #2: From Tower 1 to Tower 3
....towers(1, 2, 3)
......towers(0, 2, 1)
......Move #3: From Tower 2 to Tower 3
......towers(0, 1, 3)
..Move #4: From Tower 1 to Tower 2
..towers(2, 3, 2)
....towers(1, 3, 1)
......towers(0, 3, 2)
......Move #5: From Tower 3 to Tower 1
......towers(0, 2, 1)
....Move #6: From Tower 3 to Tower 2
....towers(1, 1, 2)
......towers(0, 1, 3)
......Move #7: From Tower 1 to Tower 2
......towers(0, 3, 2)


How to do this?
The specs require a precise format for the stdout output. Thus we are not allowed to print
this additional information to stdout. We opt to use stderr.
The C code
The C source code to do this is shown here:
/* Author: kclowes */
/* Description: Solves "Towers of Hanoi" problem.
 * Prints sequence of moves to stdout.
 * Prints other information tracing the
 * algorithm's progress to stderr.
 */
#include <stdio.h>
#include "towers.h"
static void showRecursionDepth(void);
static unsigned int depth = 0;
static unsigned int moveNumber = 0;
void towers(unsigned int n, unsigned int from, unsigned int dest)
{
 unsigned int spare = 6 - from - dest;
 showRecursionDepth();
 fprintf(stderr, "towers(%d, %d, %d)\n", n, from, dest);
 depth++;
 if (n != 0) {
 towers(n-1, from, spare);
 showRecursionDepth();
 fprintf(stderr, "Move #%d: From Tower %d to Tower %d\n",
 ++moveNumber, from, dest);
 printf("%d %d\n", from, dest);
 towers(n-1, spare, dest);
 }
 depth--;
}
static void showRecursionDepth()
{
 int i;
 for(i = 0; i < depth; i++)
 fprintf(stderr, "..");
}

Compile and run towers
You do not need to type in any of the C source code files; you got copies of the necessary
files when you copied the "needed" files for the lab.
Create the executable towers with the command:
gcc -o towers towers.c towersMain.c
You can now run the program with the command:
towers
Lots of lines of information will be displayed on the command line window. The next
section explains how you can view what is of interest.
Separating stdout and stderr
We have seen previously that the stdout stream using the > symbol. Try it with the towers
command as follows:
towers > junk1
You will still see the quite verbose output written to stderr but the output written to stdout
will no longer appear on the screen (and mixed up with stderr); instead, it is put into the file
junk1 (where you can view it at your leisure).
It is also possible to redirect stderr with the two-character symbol 2>. For example, we can
do the opposite of the previous example (seeing stdout on the screen and re-directing stderr
to a file) with the command:

 towers 2> junk2


You can also redirect both stdout and stderr at the same time; in this case, each will be
written to a separate file and nothing will appear on the screen. Try the following command

towers 2> details > pureStdout

Requirement 1
Answer these questions in your README file.
Question:
Suppose that towers(5, 2, 3) is invoked.
1. How will the first recursive call to towers() be invoked? Answer this
question in the form: towers(x, y, z) where you give the actual values to the
three parameters.
2. How many recursive calls to towers() will be made before this first recursive
call actually returns to the initial invocation?
3. Once towers(5, 2, 3) has invoked its first recursive call to towers() and this
invocation has returned, what will be printed to stdout? (i.e. What actual
move will be made by towers(5, 2, 3) ?)
4. How will the second recursive call to towers() be invoked? Answer this
question in the form: towers(x, y, z) where you give the actual values to the
three parameters.
Question:
Suppose that towers(8, 1, 2) is invoked. How many lines will be printed to stdout?
Note
• You should note (or try to convince yourself) that the number of lines printed
to stdout is precisely equal to the number of moves required to solve the
problem.
• You can use the theoretical analysis of the problem to determine the number
of moves.
• The towers command behaves somewhat differently than what has been
described so far. In particular, if it is invoked with an argument, it will move
the specified number of disks from Tower 1 to Tower 2. For example,

 towers 10


will output the actions to move 10 disks.
• Of course, you can redirect the moves to a file and then count the number of
lines in the file, allowing you to use the software to verify your theoretical
answer.
• Instead of counting the lines manually, you can use the Unix command wc -l
someFile to do the work for you.
Tutorial II: The main() function
Specifications for the towers command
NAME
towers—towers of Hanoi solver
SYNOPSIS
towers numberDisks fromTower destTower
DESCRIPTION
Solves the Towers of Hanoi problem and prints the required moves to stdout. One line of
text in the format FromTowerID ToTowerID is written for each move. The TowerIDs are '1'
(for left tower), '2' (for middle tower) or '3' (for right Tower).
The program behaves as follows depending on the arguments given on the command line:
No arguments
If no arguments are given, the problem is solved for moving 3 disks from Tower 1 to
Tower 2.
One argument (numberDisks)
If only one argument is given, the problem is solved for moving numberDisks disks
from Tower 1 to Tower 2.
Three arguments (numberDisks fromID toID)
If all three arguments are given, the problem is solved for moving numberDisks
disks from Tower fromID to Tower toID. The tower IDs must be either '1', '2' or '3'
and the two IDs must be different.
EXIT CODE
If the command is invoked correctly, the moves are output and the exit status is 0 (zero).
Otherwise, an incorrect invocation produces no output. A message is displayed on stderr
and the exit status is non-zero.
BUGS
The program does not yet behave as specified. The command line args to identify the two
towers are not recognized. Furthermore, incorrect invocation is not detected.
Initial version of main()
You are provided with an initial version of the main() function in the file towersMain.c and
the listing is shown below. However, the bugs identified in the previous section can be fixed
in the main() function.
#include <stdlib.h>
#include "towers.h"
int main(int argc, char **argv)
{
 int n = 3;
 int from = 1;
 int dest = 2;
 if (argc > 1) {
 n = atoi(argv[1]);
 }
 towers(n, from, dest);
 exit(0);
}
Requirement 2
You have to modify the main() function so that the bugs identified are fixed. The file
containing the main function must still be calledtowersMain.c; i.e. you edit the existing file
to fix the bugs.
Lab Submission
README file
Your README file should contain:
1. A brief description of what you did (and did not) achieve in the Lab.
2. Your answers to the Questions in Requirement 1.
Submit your lab
1. Go to your coe428 directory
2. Zip your lab2 directory by using the following command:
 zip -r lab2.zip lab2/
3. Submit the lab2.zip file using the following command:
 submit coe428 lab2 lab2.zip
by Ken Clowes, revised by Olivia Das