Thread: Need help with understanding a recursion function

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    19

    Need help with understanding a recursion function

    Code:
    void dohanoi(int N, int from, int to, int using) 
    {
             if (N > 0) 
            { 
                   dohanoi(N-1, from, using, to);                //1
                   printf ("move %d --> %d\n", from, to);  //2 
                   dohanoi(N-1, using, to, from);               //3
            } 
    } 
    
    dohanoi(4, 1, 3, 2);
    I know most have you have seen this Towers of Hanoi recursive function before so hopefully someone'll be able to shed some light in how it works.

    When dohanoi() is called how does it all exactly work? I'm so lost. What happens when n=1 for example. I know that "1 --> 3" is printed but I'm exactly sure why?

    How is it that anything even happens when n=1? I mean, the first line of the if statement is to call
    Code:
    dohanoi(N-1, from, using, to);
    . Shouldn't it go back to the top with the function now being
    Code:
    dohanoi(0, 1, 2, 3)
    ? And then nothing happen? Why does //2 happen?

    I would love it if someone could break down what's going on for n=1 and maybe n=2 and n=3 too.

    I've looked at a factorial recursion example and it was quite simple understand, but this Tower one just isn't making sense to me. I think part of it is that it's a void function and secondly that there are multiple things under the if statement. I think I'm making more difficult than it is, but I just transferred schools and am frustrated to see that my previous school left me under prepared for this semester's courses. I'm feeling a bit overwhelmed.
    Last edited by CS_Student8337; 02-07-2009 at 03:45 PM.

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    for n== 0 function checks if conditions and does nothing

    for n == 1 function calls
    itself for n == 0 (which does nothing)
    moves 1 piece from "from" bar to "to" bar (notifying user with printf)

    and calls itself for n==0 once again, which again does nothing


    So summurizing

    n==0 - do nothing
    n == 1 - move circle "from" --> "to"
    n==2 - could you investigate yourself?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    19
    Thanks for the quick response. I think that it's making a bit more sense.

    So for n=1 the if statement triggers, the function calls itself for 0, the if statement DOESN'T trigger. Then the print statement executes. Then that second function call happens but why is it for 0 again, with nothing happening.

    I must be missing something still because I'm still confused for n=2. Let's see:
    function calls for 2
    if statement occurs
    function calls for 1
    does it then go to the print statement to the print statement?
    and then do the second function call for 1 again?

    I imagine the output would be:
    1 --> 2
    1 --> 3
    2 -->3

    I can picture it in my head but I don't see how it happens with the dohanoi()..

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Feb 2009
    Posts
    19
    Thanks for that link. I don't have the time to check it out right this second but I'm gonna look over it tonight or tomorrow morning. From the glance I had of it, it looks like exactly what I need, but I'll be back if I have further questions.

    Thanks again

  6. #6
    Registered User
    Join Date
    Feb 2009
    Posts
    19
    Ok. I've got a pretty decent understanding of recursion itself now and am now working on my Tower program Everything's working well but I'd like to spice up my output a bit. Currently my output looks like this:

    1 ==> 3
    1 ==> 2
    2==> 3
    etc.

    But I really wanna add a counter to count the current move so that my output can be something like this

    Move 1 1 ==> 3
    Move 2 1 ==> 2
    Move 3 2==> 3
    etc.

    I've tried adding a counter in a couple of different places but it never seems to increment so my out is always

    Move 1 1 ==> 3
    Move 1 1 ==> 2
    Move 1 2==> 3
    etc.

    I've been looking on the web for the past few hours for any type of example to help me out but I just can't seem to find anything

  7. #7
    Registered User
    Join Date
    Feb 2009
    Posts
    19
    Nevermind. Global or static variable, duh

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by CS_Student8337 View Post
    Nevermind. Global or static variable, duh
    Or, perhaps just pass in another variable (as a pointer, perhaps, so that you can update the same value from all levels).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Undefined Reference Compiling Error
    By AlakaAlaki in forum C++ Programming
    Replies: 1
    Last Post: 06-27-2008, 11:45 AM
  2. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. Replies: 5
    Last Post: 02-08-2003, 07:42 PM
  5. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM