Thread: Recursive Function

  1. #1
    Registered User
    Join Date
    Mar 2017
    Posts
    2

    Recursive Function

    Hello World!

    This is my first topic in this forum. I'm trying to do tower of Hanoi where disks are moved from one tower to the next without moving all of them at once and no larger disk should be on top of the small one. I'm sure anyone studied C++ came across this challenge.

    Anyway, I'm having trouble figuring out the steps recursive function takes to come up with the result. For example how C++ uses last in first out(LIFO) in the function that calls itself in two places? or what is the order functions are called?

    For making the matter easier to understand I have made a spreadsheet with all the steps (that I could guess) in red, but I stuck after step 18.

    Can someone please help me out on this?
    Thanks

    Here's the link that you can download the steps I tried to figure out:

    https://www.dropbox.com/s/9xaxelosg75ycc6/Function%20Call.xlsx?dl=0

    Here's the code:

    Code:
    #include <iostream>
    using namespace std;
    
    void move_rings(int n, int src, int dest, int other);
    void move_a_ring(int src, int dest);
    
    int main()
    {
    int n = 3; // Stack is 3 rings high
    move_rings(n, 1, 3, 2); // Move stack 1 to stack 3
    return 0;
    }
    void move_rings(int n, int src, int dest, int other) {
    if (n == 1) {
    move_a_ring(src, dest);
    } else {
    move_rings(n - 1, src, other, dest);
    move_a_ring(src, dest);
    move_rings(n - 1, other, dest, src);
    }
    }
    
    void move_a_ring(int src, int dest) {
    cout << "Move from " << src << " to " << dest << endl;
    }






  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Not sure how you need 18 steps for something with only 7 steps.

    Besides, get creative and add some debug statements.
    Code:
    void move_rings(int n, int src, int dest, int other) {
      const char *indent = "    ";
      cout << &indent[n] << "Call(" << n << "," << src << "," << dest << "," << other << ")" << endl;
    if (n == 1) {
    move_a_ring(src, dest);
    } else {
    move_rings(n - 1, src, other, dest);
    move_a_ring(src, dest);
    move_rings(n - 1, other, dest, src);
    }
      cout << &indent[n] << "Retn(" << n << "," << src << "," << dest << "," << other << ")" << endl;
    }
    
    
    $ g++ foo.cpp
    $ ./a.out 
     Call(3,1,3,2)
      Call(2,1,2,3)
       Call(1,1,3,2)
    Move from 1 to 3
       Retn(1,1,3,2)
    Move from 1 to 2
       Call(1,3,2,1)
    Move from 3 to 2
       Retn(1,3,2,1)
      Retn(2,1,2,3)
    Move from 1 to 3
      Call(2,2,3,1)
       Call(1,2,1,3)
    Move from 2 to 1
       Retn(1,2,1,3)
    Move from 2 to 3
       Call(1,1,3,2)
    Move from 1 to 3
       Retn(1,1,3,2)
      Retn(2,2,3,1)
     Retn(3,1,3,2)
    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.

  3. #3
    Registered User
    Join Date
    Mar 2017
    Posts
    2
    This helped me a lot. I did not know you could debug like that. Can you also tell me why there are 2 returns Retn(1,3,2,1) and Retn(2,1,2,3)?

    Thanks

  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
    > Can you also tell me why there are 2 returns Retn(1,3,2,1) and Retn(2,1,2,3)?
    Because there are two matching calls earlier on.

    Here's another way to look at recursion.
    I assume you're familiar with factorial - eg 4! = 4 * 3 * 2 * 1
    Code:
    int factorial ( int n ) {
      if ( n == 0 ) return 1;
      else return n*factorial(n-1);
    }
    Another long winded and pointless way to write this would be
    Code:
    int factorial0( ) {
      return 1;
    }
    int factorial1( ) {
      return 1 * factorial0();
    }
    int factorial2( ) {
      return 2 * factorial1();
    }
    int factorial3( ) {
      return 3 * factorial2();
    }
    int factorial4( ) {
      return 4 * factorial3();
    }
    The recursive function just pushes the number to be a parameter to the function (and re-uses the same code over and over).

    When these code examples are run in a debugger, and stack traces printed out, this is what you might see.
    Code:
    $ gdb -q ./a.out
    Reading symbols from ./a.out...done.
    (gdb) b 5
    Breakpoint 1 at 0x400537: file foo.c, line 5.
    (gdb) b 11
    Breakpoint 2 at 0x400555: file foo.c, line 11.
    (gdb) run
    Starting program: /home/sc/Documents/a.out 
    
    Breakpoint 1, factorial (n=0) at foo.c:5
    5	    return 1;
    (gdb) bt
    #0  factorial (n=0) at foo.c:5
    #1  0x000000000040054b in factorial (n=1) at foo.c:7
    #2  0x000000000040054b in factorial (n=2) at foo.c:7
    #3  0x000000000040054b in factorial (n=3) at foo.c:7
    #4  0x000000000040054b in factorial (n=4) at foo.c:7
    #5  0x00000000004005b7 in main () at foo.c:27
    (gdb) c
    Continuing.
    24
    
    Breakpoint 2, factorial0 () at foo.c:11
    11	  return 1;
    (gdb) bt
    #0  factorial0 () at foo.c:11
    #1  0x000000000040056a in factorial1 () at foo.c:14
    #2  0x000000000040057a in factorial2 () at foo.c:17
    #3  0x000000000040058c in factorial3 () at foo.c:20
    #4  0x00000000004005a4 in factorial4 () at foo.c:23
    #5  0x00000000004005d2 in main () at foo.c:28
    (gdb) c
    Continuing.
    24
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 02-18-2013, 11:01 PM
  2. Converting recursive function to tail recursive
    By ajacobs365 in forum C Programming
    Replies: 1
    Last Post: 10-30-2011, 08:15 AM
  3. Replies: 1
    Last Post: 12-03-2010, 01:54 AM
  4. Make Recursive function 'Tail-Recursive'
    By dp2452 in forum C Programming
    Replies: 7
    Last Post: 12-04-2009, 10:13 AM
  5. Recursive function
    By Fork in forum C Programming
    Replies: 3
    Last Post: 10-26-2006, 11:27 AM

Tags for this Thread