Thread: Recursive function

  1. #1
    Registered User
    Join Date
    Jul 2009
    Posts
    40

    Recursive function

    Coming from the idea of other programmers around the net I have coded this tower of hanoi solver using recursive function. The problem i'm facing is analyzing how the recursion processed the solution. As you can see I'm tracing it but I'm kinda lost now, I can only analyze the output of a recursive function using one function call but with 2 function calls ( like the code below ) I can't understand how it provided the output.



    Code:
                    //4                1              2              3
    void hanoi( int disc_num, int peg1, int peg2, int peg3 )
    {
       if( disc_num != 0 )
       {
          hanoi( disc_num - 1, peg1, peg3, peg2 ); 
          //printf( "Move the place from %d to %d\n", peg1, peg3 );
          printf( "Bottom first function call %d\n ", disc_num );
          hanoi( disc_num - 1, peg2, peg1, peg3 );
          printf( "Bottom of second call %d\n", disc_num );
       }
    }
    The output I have when I compiled and run it:

    Code:
    Bottom first function call 3
     Bottom first function call 1
     Bottom of second call 1
    Bottom first function call 2
     Bottom first function call 1
     Bottom of second call 1
    Bottom of second call 2
    Bottom of second call 3
    Bottom first function call 4
     Bottom first function call 1
     Bottom of second call 1
    Bottom first function call 2
     Bottom first function call 1
     Bottom of second call 1
    Bottom of second call 2
    Bottom first function call 3
     Bottom first function call 1
     Bottom of second call 1
    Bottom first function call 2
     Bottom first function call 1
     Bottom of second call 1
    Bottom of second call 2
    Bottom of second call 3
    Bottom of second call 4
    This is different to what I've analyzed, so I'm wrong with my analysis.

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Try to manually trace each function's call stack by building a hierarchial dependency graph.

  3. #3
    Registered User
    Join Date
    Jul 2009
    Posts
    40

    Question

    I've traced it many times but can't get it.

    Code:
    void hanoi( int disc_num, int peg1, int peg2, int peg3 )
    {
       if( disc_num != 0 )
       {
          hanoi( disc_num - 1, peg1, peg3, peg2 ); //this will be called first
             printf( "Bottom first function call %d\n ", disc_num ); //will this be executed if the first call is done?
          hanoi( disc_num - 1, peg2, peg1, peg3 ); //will this be executed if the previous statement is executed?
             printf( "Bottom of second call %d\n", disc_num ); //will this be executed if the previous statement is executed?
       }
    }
    I just have to determine which function will finish first..

  4. #4
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Try to build a very simple recursive function to understand how recursion works. This problem isn't a good one to understand recursion. This site's FAQ has nice code examples to get you up to speed on recursion.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Code:
    void hanoi( int disc_num, int peg1, int peg2, int peg3 )
    {
       if( disc_num != 0 )
       {
          hanoi( disc_num - 1, peg1, peg3, peg2 ); //this will be called first  Yep!
             printf( "Bottom first function call %d\n ", disc_num ); //will this be executed if the first call is done?  Yep!
          hanoi( disc_num - 1, peg2, peg1, peg3 ); //will this be executed if the previous statement is executed?  Yep!
             printf( "Bottom of second call %d\n", disc_num ); //will this be executed if the previous statement is executed? It'll be executed after the previous call returns
       }
    }

  6. #6
    Registered User
    Join Date
    Jul 2009
    Posts
    40
    Quote Originally Posted by itCbitC View Post
    Try to build a very simple recursive function to understand how recursion works. This problem isn't a good one to understand recursion. This site's FAQ has nice code examples to get you up to speed on recursion.
    I actually understand how recursive function works ( but only with recursive function calling itself once ) but this is my first time analyzing a recursive function calling itself twice.

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Why not something like this? :

    Code:
    void print_level( int level )
    {
       while( level-- != 0 )
       {
          putchar( '.' );
       }  
    }
    
    void hanoi_recurse( int disc_num, int peg1, int peg2, int peg3, int level )
    {
       if( disc_num-- != 0 )
       {
          print_level( level );
          printf( "hanoi( disc_num( %d ), peg1( %d ), peg3( %d ), peg2( %d ) );\n", disc_num, peg1, peg3, peg2 );      
          hanoi_recurse( disc_num, peg1, peg3, peg2, level + 1 ); 
          print_level( level );
          printf( "hanoi( disc_num( %d ), peg2( %d ), peg1( %d ), peg3( %d ) );\n", disc_num, peg2, peg1, peg3 );
          hanoi_recurse( disc_num, peg2, peg1, peg3, level + 1 );
       }
    }
    
    void hanoi( int disc_num, int peg1, int peg2, int peg3 )
    {
       hanoi_recurse( disc_num, peg1, peg2, peg3, 0 ); 
    }
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  8. #8
    Registered User
    Join Date
    Jul 2009
    Posts
    40
    Code:
                      //2
    void hanoi( int disc_num )
    {
       if( disc_num != 0 )
       {
         //first function call
          hanoi( disc_num - 1 );
             printf( "Me first\n" );
    
         //function function call
          hanoi( disc_num - 1 );
    	 printf( "Me second\n" );
       }
    }
    I've minimized the recursion to 2 and removed extra args.
    I've tried to analyze and finish the first call:

    Code:
    //first call to function
                //2
    hanoi( disc_num - 1 )
             //1
      if( disc_num != 0 )
      {
                      //1 - 1
         hanoi( disc_num - 1 )
                   //0
           if( disc_num != 0 )
           {
    
           }
    
           return //return to it's caller because disc_num == 0
    The statement "Me First" at the bottom of the first call is not yet executed until the first call has returned to it's caller?

    After the first call it'll return to it's caller then it'll call the second function call?
    Code:
    //second call to function
                 //2 <- the second function call is it 2 still or it'll get the value after function 1 which is 0? if it's 2 then proceed
    hanoi( disc_num - 1 )
             //1
      if( disc_num != 0 )
      {
                      //1 - 1
         hanoi( disc_num - 1 ) //will this be called again because of the second call ( I guess not because it's just going to return righ? )
         me first //this will be printed
                     //1 - 1
         hanoi( disc_num - 1 ) //call again
         me second //this will not be printed yet
    now I'm lost... this is ridiculous haha! I'm not taking my lunch yet because of this haha!

  9. #9
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Look at the example I posted. If you run it I think it will give you a pretty good idea of what's going on at each step.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  10. #10
    Registered User
    Join Date
    Jul 2009
    Posts
    40
    Quote Originally Posted by Sebastiani View Post
    Look at the example I posted. If you run it I think it will give you a pretty good idea of what's going on at each step.
    Thanks for the example, but my brain is not working in that example. Here's the calling I created. I don't know if this is correct or not, if it's correct then the problem I have is understanding the things that the function will return to be able to see the output. I guess I'm kinda near to the light of understanding the recursion-1 function calling itself twice.

    Code:
    Me first
    Me second
    Me first
    Me first
    Me second
    Me second
    Code:
    //parent function
                     //2
    void hanoi( int disc_num )
    {
       if( disc_num != 0 ) //will result to true because 2 != 0
       {            //2 - 1
          hanoi( disc_num - 1 );   //first call once
          printf( "Me first\n" );  //will not execute until the first call is done
          hanoi( disc_num - 1 );   //second will not execute until the first call is done
          printf( "Me second\n" ); //will not execute until the first and second call are done
       }
       //no return yet because disc_num is != 0
    }
    
    //first call once
                     //1 The value of disc num is now 1
    void hanoi( int disc_num )
    {
       if( disc_num != 0 ) //will result to true because 1 != 0
       {           //1 - 1
          hanoi( disc_num - 1 );   //first call twice
          printf( "Me first\n" );  //will not execute until the first call is done
          hanoi( disc_num - 1 );   //second will not execute until the first call is done
          printf( "Me second\n" ); //will not execute until the first and second call are done
       }
       //no return yet because disc_num is != 0
    }
    
    //first call twice
                     //0 The value of disc num is now 0
    void hanoi( int disc_num )
    {
       if( disc_num != 0 ) //will result to false because 0 == 0
       {
          hanoi( disc_num - 1 );   //will not be executed
          printf( "Me first\n" );  //will not be executed
          hanoi( disc_num - 1 );   //second will not execute because disc_num == 0
          printf( "Me second\n" ); //will not be executed
       }
       //will return to it's last caller which is the function call once because disc_num == 0
    }
    
    
    //first call twice returned to first call once
                     //1
    void hanoi( int disc_num )
    {
       if( disc_num != 0 ) //will result to true because 1 != 0
       {
          hanoi( disc_num - 1 );   //already finish
          printf( "Me first\n" );  //will be executed because first call is now done
                   //2 - 1 - it's 2 because this value came from the parent function
          hanoi( disc_num - 1 );   //second call once - because first call is now done
          printf( "Me second\n" ); //will not execute until the second call is done
       }
       //no return yet because disc_num is != 0
    }
    
    //second call once
                   //1 the value of disc in second call once is 1
    void hanoi( int disc_num )
    {
      if( disc_num != 0 ) //result to true because disc_num != 0
      {
        hanoi( disc_num - 1 );   //this is finish
        printf( "Me first\n" );  //will be executed because first call is now done
                //1 - 1
        hanoi( disc_num - 1 );  //second call twice
        printf( "Me second\n" ); //will not execute until the second call is done
      }
    
      //no return yet because disc num is != 0
    }
    
    //second call twice
                   //0 the value of disc in second call once is 0
    void hanoi( int disc_num )
    {
      if( disc_num != 0 ) //result to false because disc_num == 0
      {
        hanoi( disc_num - 1 );   //no execute
        printf( "Me first\n" );  //no execute
                //1 - 1
        hanoi( disc_num - 1 );  //no execute
        printf( "Me second\n" ); //no execute
      }
    
      //return to it's caller second call once
    }

  11. #11
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    I don't know if this helps, but here's another example:

    Code:
    void halve( char* which, int value, int level )
    {
       int
          half = value >> 1;
       print_level( level );
       printf( "enter (%s): %d\n", which, value );
       if( value != 0 )
       {          
          halve( "A", half, level + 1 );
          halve( "B", half, level + 1 );
       }
       print_level( level );
       printf( "leave (%s): %d\n", which, value );
    }
    
    
    
    int main( void )
    {	
       halve( "!", 7, 0 );
       return 0;
    }
    Last edited by Sebastiani; 07-15-2009 at 03:59 AM. Reason: indentation
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  12. #12
    Registered User
    Join Date
    Jul 2009
    Posts
    40
    After hours of writing lots of traces in recursion I now understand what actually happened. I also tried your example sebastiani, thanks so much for your sample program.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive function
    By Fork in forum C Programming
    Replies: 3
    Last Post: 10-26-2006, 11:27 AM
  2. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  3. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM