...

View Full Version : Multiple Recursion



quietIdentity
06-18-2009, 02:21 PM
Hi just wondering if anyone could clear up this multiple
recursion I'm getting in my textbook, Lewis/Chase don't discuss
it and I can't get my head around it:

private void moveTower(int numDisks, int start, int end, int temp)
{

if(numDisks==1){
moveOneDisk(Start, End);
}
else
{
moveTower(numDisks-1, start, temp, end);
moveOneDisk(Start, end);
moveTower(numDisks-1, temp, end, start);
}
}
I thought that

moveOneDisk(Start, end);
moveTower(numDisks-1, temp, end, start);

would be unreachable code as moveTower would just keep
being called.

Fatmumuhomer
06-18-2009, 03:07 PM
Those 2 lines will eventually execute, but not until numDisks finally hits the value 1. Each time moveTower runs, unless numDisks equals 1, it calls itself recursively and passes in a value for numDisks that is one lower than what was passed in.

Say moveTower() gets called and numDisks equals 3 to start. moveTower() would get called again with numDisks = 2. Then within that execution of moveTower(), it would call itself again with numDisks = 1. At that point, the base case would occur and moveOneDisk() would get called and then that moveTower() call would return. Then the moveTower() that called it would execute the next 2 lines.

Does that help?

quietIdentity
06-19-2009, 04:23 AM
Yeah kinda, so when the base case is reached for the first moveTower, moveOneDisk is called then MoveTower again which repeats the process with the parameters swapped so it starts working on the 2nd peg (This is from the Towers of Hanoi puzzle btw). That second moveTower method takes numdisks again, because a new instance with new variables etc is created each time the previous moveTower call was used numdisks in the second call refers to the original value of numdisks?

adarshakb
06-19-2009, 12:11 PM
Yeah true.. its not an unreachable code... Wat happens here is
Lets suppose
numDiscs=3,
Start=1
end=3
temp=2;
----------------------------------------------------
THIS IS THE FOLLOW UP
----------------------------------------------------
STEP 1:eek:
private void moveTower(3, 1, 3, 2)
{
if(numDisks==1){//FALSE
else
{
moveTower(2, 1, 2, 3);
-------------
STEP 2:eek:
private void moveTower(2, 1, 2, 3)
{
if(numDisks==1){//FALSE
else
{
moveTower(1, 1, 3, 2);
--------------
STEP 3:eek:
private void moveTower(1, 1, 2, 3)
{
if(numDisks==1){//TRUE **
moveOneDisk(1,2);}
// END OF FUNCTION
--------------
GOTO STEP 2 FUNCTION
{
moveOneDisk(1, 2);
moveTower(1, 3, 2, 1);
--------------
STEP 4:eek:
private void moveTower(1, 3, 2, 1)
{
if(numDisks==1){//TRUE **
moveOneDisk(3,2);}
// END OF FUNCTION
--------------
GOTO STEP 2 FUNCTION
// END OF FUNCTION
--------------
GOTO STEP 1 FUNCTION:cool:
moveOneDisk(1, 3);
moveTower(2, 2, 3,1);
--------------
STEP 5;)
private void moveTower(2,2,3,1)
{
if(numDisks==1){//FALSE
else
{
moveTower(1,2,1,3);
--------------
STEP 6
private void moveTower(1, 2, 1, 3)
{
if(numDisks==1){//TRUE **
moveOneDisk(2,1);}
// END OF FUNCTION
--------------
GOTO STEP 5 FUNCTION;)
{
moveOneDisk(2, 1);
moveTower(1, 1,3, 2);
--------------
STEP 7
private void moveTower(1,1, 3, 2)
{
if(numDisks==1){//TRUE **
moveOneDisk(1,3);}
// END OF FUNCTION
---------------
GOTO STEP 5FUNCTION
// END OF FUNCTION
--------------
GOTO STEP 1 FUNCTION
//END OF FUNCTION

//END OF PROGRAM:thumbsup:

P.S.: Its Confusing to copypaste codes.. lol if there is a mistake sorry..
But this is the general idea of the program...
NO problem in it:thumbsup:

Fatmumuhomer
06-19-2009, 04:02 PM
Yeah kinda, so when the base case is reached for the first moveTower, moveOneDisk is called then MoveTower again which repeats the process with the parameters swapped so it starts working on the 2nd peg (This is from the Towers of Hanoi puzzle btw). That second moveTower method takes numdisks again, because a new instance with new variables etc is created each time the previous moveTower call was used numdisks in the second call refers to the original value of numdisks?

I think you got it. And adarshakb's post is very nice for mapping it out. The variables used all have local scope within each call of the moveTower() function. When moveTower() is called from itself, all of the variables get created just for that instance of moveTower(). When the lowest instance of moveTower() finishes (because the base case is true), then it returns to the instance of moveTower() that called it and that instance continues executing.



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum