# Thread: Recursive function

1. ## 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. Try to manually trace each function's call stack by building a hierarchial dependency graph.

3. 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. 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. 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. 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.

7. 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 );
}```

8. 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. 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.

10. 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
}```

11. 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;
}```

12. 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