Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 5 of 5
  1. #1
    New to the CF scene
    Join Date
    Jun 2009
    Posts
    2
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Multiple Recursion

    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.

  • #2
    New Coder
    Join Date
    Jun 2006
    Posts
    30
    Thanks
    2
    Thanked 1 Time in 1 Post
    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?

  • Users who have thanked Fatmumuhomer for this post:

    quietIdentity (06-19-2009)

  • #3
    New to the CF scene
    Join Date
    Jun 2009
    Posts
    2
    Thanks
    1
    Thanked 0 Times in 0 Posts
    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?

  • #4
    Regular Coder adarshakb's Avatar
    Join Date
    Jun 2009
    Location
    Silicon valley of india
    Posts
    247
    Thanks
    11
    Thanked 1 Time in 1 Post

    Post

    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
    private void moveTower(3, 1, 3, 2)
    {
    if(numDisks==1){//FALSE
    else
    {
    moveTower(2, 1, 2, 3);
    -------------
    STEP 2
    private void moveTower(2, 1, 2, 3)
    {
    if(numDisks==1){//FALSE
    else
    {
    moveTower(1, 1, 3, 2);
    --------------
    STEP 3
    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
    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
    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

    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

  • #5
    New Coder
    Join Date
    Jun 2006
    Posts
    30
    Thanks
    2
    Thanked 1 Time in 1 Post
    Quote Originally Posted by quietIdentity View Post
    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.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •