# Recursive function

• 07-14-2009
WatchTower
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.
• 07-14-2009
itCbitC
Try to manually trace each function's call stack by building a hierarchial dependency graph.
• 07-14-2009
WatchTower
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..
• 07-14-2009
itCbitC
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.
• 07-14-2009
itCbitC
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   } }```
• 07-14-2009
WatchTower
Quote:

Originally Posted by itCbitC
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.
• 07-14-2009
Sebastiani
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 ); }```
• 07-14-2009
WatchTower
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!
• 07-14-2009
Sebastiani
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.
• 07-15-2009
WatchTower
Quote:

Originally Posted by Sebastiani
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 }```
• 07-15-2009
Sebastiani
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; }```
• 07-15-2009
WatchTower
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.