Question
Recursion in C ---------------------------------------------------------------------------------- We examine the classic Towers of Hanoi algorithm here and answer some questions based on the information provided. Specifications for executable
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
- Suppose that towers(5, 2, 3) is invoked.
- 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.
- How many recursive calls to towers() will be made before this first recursive call actually returns to the initial invocation?
- 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) ?)
- 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.
- 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.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started