Recursion in C

----------------------------------------------------------------------------------

We examine the classic Towers of Hanoi algorithm here and answer some questions based on the information provided.

Specifications for executable

• Towers are identified with a single integer: the left, middle and right towers are named as '1', '2' and '3' respectively.
• The program includes 3 files: towers.h, towers.c, towersMain.c. The codes for these 3 files are given below.

Code for towers.h :

void towers(unsigned int numOfDisks, unsigned int fromID, unsigned int destID);

Code for towers.c :

/* 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

#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, from, dest);

depth++;

if (n != 0) {

towers(n-1, from, spare);

showRecursionDepth();

fprintf(stderr, "Move #%d: From Tower %d to Tower %d ", ++moveNumber, from, dest);

printf("%d %d ", from, dest);

towers(n-1, spare, dest);

}

depth--;

}

static void showRecursionDepth()

{

int i;

for(i = 0; i

fprintf(stderr, "..");

}

Code for towersMain.c :

#include

#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);

}

Compile and Run

Create the executable towers with the command: gcc -o towers towers.c towersMain.c

You can now run the program with the command: towers

Output of the program

After you run the program, it will print the following. Please note that the output is written to stderr.

Separating stdout and stderr

If you type the following command: towers > junk1

The program will still print the output written to stderr. However the output written to stdout will appear in a file named junk1 and it is given below:

1 2

1 3

2 3

1 2

3 1

3 2

1 2

ANSWER THE FOLLOWING QUESTIONS BASED ON THE INFORMATION GIVEN ABOVE AND SHOW YOUR WORK

1. 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.

2. Suppose that towers(8, 1, 2) is invoked. How many lines will be printed to stdout?

• Note that the number of lines printed to stdout is precisely equal to the number of moves required to solve the problem.
• Use the theoretical analysis of the problem to determine the number of moves.
• You can redirect the moves to a file and then count the number of lines printed to stdout in that file, allowing you to verify your theoretical answer. Instead of counting the lines manually, you can also use the Unix command: wc -l someFile to do the work for you.

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 l 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 Towe 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 l to Tower 2 ...... towers (0, 3, 2) 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 l 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 Towe 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 l to Tower 2 ...... towers (0, 3, 2)