Recursion is simply put the ability of a function to recursively call itself. Re
ID: 665520 • Letter: R
Question
Recursion is simply put the ability of a function to recursively call itself. Recursion is quite easy and also quite practical. Just don't forget to put in an exit clause to your recursive functions or you will find yourself staring at a spinning hourglass while the algorithm chews up all your available resources.
The classic example of a recursive solution to a relatively complex problem is the Tower of Hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi - which is taught in every Computer Science program and in a lot of programming classes. As you add disks the solution becomes more complex, but it is a simple repetition of moves used in the 3 disk solution.
Assignment
We are not going to solve Tower of Hanoi, you are simply going to write a program to demonstrate computational complexity. Using the wikipedia article I want you to write a computer program in Javascript using JSFiddle that calculates the number of moves necessary to solve Tower of Hanoi given a number of disks. Should we be concerned with concerned with the legend of the world ending when the 64 disk solution is physically solved? Please post your complete code and screenshots if possible. Thank you.
Explanation / Answer
The tower of hanoi can be resolved with these steps :
Length(N) = 3·Length(N-1) + 1 and Length(1) = 1. '
integer parametres :
1st Method :
<!-- TWO STEPS TO INSTALL TOWERS OF HANOI:
1. Put the designated coding into the HEAD of your HTML document
2. Paste the last code into the BODY of your HTML document -->
<!-- STEP ONE: Copy this code into the HEAD of your HTML document -->
<HEAD>
<SCRIPT LANGUAGE="JavaScript">
<!-- Begin
var maxHeight=7;
var numTurns=0;
var necTurns=Math.pow(2, maxHeight)-1;
function makeTowerA() {
var i;
for(i=0; i < maxHeight; i++)
this[i]=i+1;
this.height=maxHeight;
return this;
}
function makeTowerBC() {
var i;
for(i=0; i < maxHeight; i++)
this[i]=0;
this.height=0;
return this;
}
function towerArray() {
this[0]=new makeTowerA();
this[1]=new makeTowerBC();
this[2]=new makeTowerBC();
return this;
}
var towers=new towerArray();
function disc(num) {
var i;
var discString="";
var whiteSpace=" ";
if (num > 0) {
discString="#";
i=2;
while(i <= num) {
discString+="##";
i++;
}
}
return whiteSpace.substring(0, maxHeight-num) + discString;
}
function writeTowers() {
var i, j;
for(j=0; j < 3; j++)
for(i=0; i < maxHeight; i++)
document.hanoi.elements[j * (2 + maxHeight) + i + 2].value=disc(towers[j][i]);
}
function moveDisc(fromTower, toTower) {
if (towers[fromTower].height == 0) {
alert("Tower doesn't have discs to move!");
return;
if (towers[toTower].height != 0)
if (towers[toTower][maxHeight-towers[toTower].height] <= towers[fromTower][maxHeight-towers[fromTower].height]) {
alert("Illegal move!");
return;
}
towers[toTower][maxHeight-towers[toTower].height-1]=towers[fromTower][maxHeight-towers[fromTower].height];
towers[fromTower][maxHeight-towers[fromTower].height]=0;
towers[toTower].height++;
towers[fromTower].height--;
numTurns++;
writeTowers();
if (towers[1].height == maxHeight)
alert("You solved it! " + "In " + (numTurns - necTurns) + " more turn(s) than necessary!");
}
function writeTower() {
var i;
for(i=0; i < maxHeight; i++) {
document.write('<tr><td align=center><input type="text" size=');
document.write(2*maxHeight-1);
document.write('></td></tr>');
}
}
// End -->
</SCRIPT>
<!-- STEP TWO: Paste this code into the BODY of your HTML document -->
<BODY>
<CENTER>
<FORM name="hanoi">
<TABLE cellspacing="0" cellpadding="0" align="left">
<TR><TD align="center"><font size="+3" color="#ff0000">Tower A</font></TD><TR>
<TR><TD><input type="button" value="to C">
<input type="button" value="to B"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
</TABLE>
<TABLE cellspacing="0" cellpadding="0" align="right">
<TR><TD align="center"><font size="+3" color="#ff0000">Tower B</font></TD><TR>
<TR><TD><input type="button" value="to A">
<input type="button" value="to C"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
</TABLE>
<BR><BR><BR>
<CENTER>
<TABLE cellspacing="0" cellpadding="0">
<TR><TD align="center"><font size="+3" color="#ff0000">Tower C</font></TD><TR>
<TR><TD><input type="button" value="to A">
<input type="button" value="to B"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
<TR><TD align="center"><input type="text" size="13"></TD></TR>
</TABLE>
</CENTER>
</FORM>
Second method :
var callcallStack;
function executeHanoi()
{ // Some initialization code goes here
callStack=[]; // callStack array is global
Hanoi(diskCount, 0,2,1);
moveDisk(); // moveDisk takes its parameters from callStack
}
function moveDisk()
{ if (callStack.length==0) return;
var param = callStack.shift(); // Get call parameters from callStack
// Note: throughout the code, I use fromBar, toBar to refer to towers
fromBar = param[0];
toBar = param[1];
// find top element in fromBar
var elem = document.getElementById(barsInfo[fromBar].disks.pop());
moveInfo = { elem: elem,
fromBar: fromBar,
toBar: toBar,
whichPos: "top", // element position property for movement
dir: -1, // 1 or -1
state: "up", // move upward
endPos:60 // end position (in pixels) for move upward
}
myTimer = setInterval(animateMove,speed); // Start animation
}
function animateMove()
{ var elem = moveInfo.elem;
var dir = moveInfo.dir;
var styleInfo = window.getComputedStyle(elem);
var pos = parseInt(styleInfo[moveInfo.whichPos]);
if (((dir==1) && (pos >= moveInfo.endPos)) ||
((dir==-1) && (pos <= moveInfo.endPos)))
{ // alert(moveInfo.state);
if (moveInfo.state == "up")
{ moveInfo.state = "hor";
moveInfo.whichPos ="left";
moveInfo.dir = 1;
if ( moveInfo.fromBar > moveInfo.toBar) moveInfo.dir = -1;
//alert("toBar:" + moveInfo.toBar);
var toBar = document.getElementById("bar"+ moveInfo.toBar);
// alert(toBar.offsetLeft);
moveInfo.endPos = toBar.offsetLeft -
Math.floor(elem.offsetWidth/2)+15; // 15 is half of tower width
return;
}
else if (moveInfo.state == "hor" ) // move down
{ // alert("here");
moveInfo.state = "down";
moveInfo.whichPos ="top";
moveInfo.dir = 1;
//alert(elem.offsetHeight);
moveInfo.endPos = document.getElementById("bottombar").offsetTop -
(barsInfo[moveInfo.toBar].disks.length+1)*elem.offsetHeight;
return;
}
else // end of current call to moveDisk, issue next call
{ clearInterval(myTimer); // cancel timer
barsInfo[moveInfo.toBar].disks.push(elem.id);
moveDisk();
return;
}
}
pos = pos + dir*moveInc;
elem.style[moveInfo.whichPos] = pos+ "px";
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.