Recursion: Towers of Hanoi

[TheCoolest2]

Hello everyone. So I'm required for my assignment to create a recursion function that can solve the towers of Hanoi puzzle along with creating command line arguments. So far I've done the arguments and as for the recursion call I've done the base case, which I believe to be having 1 disk, you just need to move it. Now my professor gave a tip today that so lets say you have n disks, and n was 4. So you begin with n-1, which will be 4-1=3, and then he said you move those 3 disks to whichever of the other 2 pegs. What I was confused about was how you can move 3 if you are only allowed to move 1 disk at a time. I tried to ask but he had to move on. First if you get the number 3 back, how does it know its 3 disks? Technically its just 1 integer thats named 3, I'm thinking the use of an array/vector, but the program doesn't have a predefined amount of disks, its whatever the user inputs. So how would you go about that? He said to try to draw a recursion tree but I missed the class he discussed it because my dad is real sick, so unfortunately didn't catch it. Thanks

NOTE: The else statement in my puzzleSolver function was just a test, it's not a part of the program and the notes at the bottom is just for me.

// TODO: write the program.
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <getopt.h> // to parse long arguments.
#include <cstdlib> // for atoi function

int puzzleSolver(long disks,long startPeg,long);

/* Here's a skeleton main function for processing the arguments. */
int main(int argc, char *argv[]) {
	// define long options
	long disks;
	long startPeg;
	long endPeg;
// I REMOVED THE COMMAND ARGUMENTS INCASE ANYONE FROM CLASS IS SEARCHING THIS UP AND COPIES :p IF YOU NEED IT POSTED ASK

	/* TODO: now that you have the options and arguments,
	 * solve the puzzle. */
	puzzleSolver(disks, startPeg, endPeg); // Just testing
}

int puzzleSolver(long disks ,long startPeg ,long endPeg ){
	if(disks == 1)
		cout << "Move disk " << disks << " to peg " << endPeg << endl;
	else{
		puzzleSolver(disks -1, startPeg, endPeg);
		cout << "Move " << disks << " to peg " << endPeg << endl;

	}
}
//Pass by value to pass very small objects ex f(int x)
//Pass by const reference to pass large objects that you don't modify f(const int x)
//return a result rather then modifying an object thhrough a reference argument
//use pass by reference only when you have to f(int& x)
//constexpr evaluates function at compile time. must have a single return statement, cant change values outside of its body, except those assigned to or uses to intialize

[suitedupvet83]

what your instructor meant was to solve the problem with 3 disks by stacking disks numbers 1,2,and 3 in either peg B or C. Then you can solve for n=4 by moving the 4th disk from the source peg (A) to the unused peg then use the same method for 3 disks to stack those 3 disk on top of disk number 4. If you don't know how to solve for 3, then solve for 2 first. (This demonstrates the recursion part of the problem)

It knows that its 3 disks because you tell them program its 3 disk.. either by hardwiring it into the code so it will always be 3 disks or a cout<<"How many disk?; cin>> disks; where disks is an integer and the user can enter 3, or whatever number.

You don't need an array or vector to solve this. That would be just making it too dificult

[TheCoolest2]

Hello. Thanks for the reply. So before I saw your reply I actually did rewrite my program.
As for the "It knows that its 3 disks". Yah thats the part I didn't include in my code, its part of the programs arguments. I have it cin >> disks;. There's also arguments to determine the start and ending peg. So what I did was create another function to keep things clean that will determine the unused peg. Now I will do the recursive. Thanks for the explanation I'll get back to you

[TheCoolest2]

Hello. I'm typing this out again after my page glitched out -_-. Anyways, its been hours since I've been trying to draw out the logic on paper and program it in, and here's what I got

int puzzleSolver(long disks, long startPeg, long usingPeg, long endPeg ){
	if(disks == 1){
		cout << "NOTE THIS LINE IS BASE CASE :Move disk from"<< startPeg << " to peg " << endPeg << endl;
	}
	else{
		cout << "Move disk from " << startPeg << " to peg " << endPeg << endl;
		puzzleSolver(disks-1,startPeg,endPeg,usingPeg);
		cout << "Move disk from " << startPeg << " to peg " << endPeg << endl;
		puzzleSolver(disks-1,usingPeg,startPeg,endPeg);
	}
}

int usingPegChecker(long disks, long startPeg, long usingPeg, long endPeg){
	if(startPeg == 1 && endPeg == 3){
		usingPeg = 2;
		cout << "Checking usingPeg with startPeg = 1 and endPeg = 3 ---- " << usingPeg << endl;
		puzzleSolver(disks, startPeg, usingPeg, endPeg);
	}

I only included part of the usingPegChecker because I'm only using the parameters of 3 disks(easier to test), starting on the first peg, and moving everything to the third one.

So the program should be taking 7 steps ((2^disks)-1). This is the output
Checking usingPeg with startPeg = 1 and endPeg = 3 ---- 2
Move disk from 1 to peg 3
Move disk from 1 to peg 2
NOTE THIS LINE IS BASE CASE :Move disk from1 to peg 3
Move disk from 1 to peg 2
NOTE THIS LINE IS BASE CASE :Move disk from3 to peg 2
Move disk from 1 to peg 3
Move disk from 2 to peg 3
NOTE THIS LINE IS BASE CASE :Move disk from2 to peg 1
Move disk from 2 to peg 3
NOTE THIS LINE IS BASE CASE :Move disk from1 to peg 3


Now i'm assuming the base case is the problem, but if I change it I don't think it will function correctly if someone just tries the program with the parameter of 1 disk.

As how this function is being called, after the getopt tags in main, I'm calling on the usingPegChecker passing in the arguments, and then as you see that calls on the puzzleSolver. Any help would be appreciated :)