Pre print recursion | Chinese Rule of Eight

ref – http://chineseruleof8.com/code/index.php/2015/11/16/simple-recursion/

void countDown( int n ) {

//SOL #1

if(n == 0){ // BASE CASE #2

printf("\n\n ~~~ HAPPY NEW YEARRRRRR! ~~~~ "); //#3

return; //EOL #4

}

printf("\n\n %d !", n); // #5

countDown(n-1); //#6

//EOL #7

}

note: recFunc is a placeholder name for any recursive function name that you are running.

a) we write the push of the function for recFunc( 3 ) onto the main stack
b) We begin for the start of line for recFunc( 3 ) at comment #1
c) We check the base case at comment #2, it is false so we move down to comment #5. Its a print statement so we print n, which is 3.

We need to remember to write 3 in the output as shown on the top right hand side of the image.

Then we hit comment #6, which is a call to the recursive function. This means we are going to push recRunc( 2 ) onto the stack. Thus:

a) we for visual clarity, we tab some spaces, then write out recFunc( 2 )
b) we reach comment #1 which is the Start Of Line for recFunc( 2 )
c) We check the base case at comment #2, it is false so we move down to comment #5. Its a print statement so we print n, which is 2. Remember to write it in your output section.

Reaching the base case

We continue this fashion until we hit recFunc( 0 ). Once we get to recFunc( 0 ), we write out SOL at comment #1, then when we reach the base case at comment #2. It evaluates to true, so we print out the “happy new year” at comment #3, and the function returns at comment #4.

Whenever a return or end of function is reached, we pop the stack frame. In our case we pop the stack frame for recFunc( 0 ). On our paper for visual clarity, make sure you draw a line connecting SOL 0 to EOL 0. This tells us that the stack frame for rechFunc has been popped and completed.

In code, we then continue where we left off at comment #6 for recFunc( 1 ). We then go down to comment #7. Its the EOL for recFunc( 1 ), so on our paper, we write out —– EOL 1 —–.

In code, we reach end of function, so that means we pop the stack frame for recFunc( 1 ). Make sure you draw the connecting line from SOL 1 TO EOL 1 to clarify this.

We continue where we left off at comment #6 for recFunc( 2 )…

We keep doing this until all the stack frames have been popped, and we finish running recFunc( 3 ).

Thus, in the output, you should see: 3 2 1 Happy New Year!