recursive function question

[adam2016]

Hi everyone,I'm on a chapter of recursion at the moment but the books example is poorly explain and I still don't know what is happening with this code,

for example when I run this it will print as follows

hello
hello
hello
hello
hello
hello
BYE
middle
BYE
middle
BYE
middle
BYE
middle
BYE
middle
BYE

also I have a few questions why is hello printed 6 times before any other code and more importantly why is BYE printed before middle when middle is actually before BYE in my code plus why is middle only printed out 5 times as opposed to 6 times like hello and BYE?

thanks

  #include <iostream>

using namespace std;


void buildWall(int height);

int main()
{
    buildWall(5);

}

void buildWall(int height){


      cout << "hello " << endl;

      if(height > 0){

       buildWall(height - 1);
       cout << "middle" << endl;
      }

      cout << "BYE" << endl;

}

[lastchance]

It starts buildWall with parameter 5
***- which says hello and starts buildwall with parameter 4
******- which says hello and starts buildwall with parameter 3
*********- which says hello and starts buildwall with parameter 2
************- which says hello and starts buildwall with parameter 1
***************- which says hello and starts buildwall with parameter 0
***************- which says just hello and BYE and returns
************- so buildwall with parameter 1 can now say middle and BYE and return
*********- so buildwall with parameter 2 can now say middle and BYE and return
******- so buildwall with parameter 3 can now say middle and BYE and return
***- so buildwall with parameter 4 can now say middle and BYE and return
- so buildwall with parameter 5 can now say middle and BYE and return


Fundamentally, cout >> "middle" is inside the loop which is only called the 5 times that the parameter is > 0. hello and BYE are output all 6 times that the function is called.

It might be a bit easier to see when starting with a smaller parameter than 5.

[Chervil]

It can be helpful to use indentation to identify which call is generating which output.
Example:

#include <iostream>
#include <string>

using namespace std;

void buildWall(int height);

int main()
{
    buildWall(5);
}

void buildWall(int height)
{
    string spacer(height*4, '.'); 

    cout << spacer << "hello " << endl;
    
    if (height > 0)
    {
        buildWall(height - 1);
        cout << spacer << "middle" << endl;
    }
    
    cout << spacer << "BYE" << endl;

}

Output:

....................hello
................hello
............hello
........hello
....hello
hello
BYE
....middle
....BYE
........middle
........BYE
............middle
............BYE
................middle
................BYE
....................middle
....................BYE

[adam2016]

thanks for the help guys


I'm still kind of confused I get why hello is printed 6 times because hello is before the recursive call and control does not go past the buildwall function call thus it is printed 6 times I understand that BUT once buildwall(0) happens why does hello not get printed again(another 5 times)?

It starts buildWall with parameter 5
***- which says hello and starts buildwall with parameter 4
******- which says hello and starts buildwall with parameter 3
*********- which says hello and starts buildwall with parameter 2
************- which says hello and starts buildwall with parameter 1
***************- which says hello and starts buildwall with parameter 0
***************- which says just hello and BYE and returns
************- so buildwall with parameter 1 can now say middle and BYE and return
*********- so buildwall with parameter 2 can now say middle and BYE and return
******- so buildwall with parameter 3 can now say middle and BYE and return
***- so buildwall with parameter 4 can now say middle and BYE and return
- so buildwall with parameter 5 can now say middle and BYE and return

I understand why hello and BYE are printed at first but I don't get why buildwall with parameter 1 to 5 can say middle and BYE and return,


what I'm trying to say is why does control go to line 22 after hello is printed out why does the function not get run in it's entirety starting with hello again?

thanks

[lastchance]

Nothing can start returning ("unwinding") until a NON-RECURSIVE call is made (to buildWall(0) - the only one that doesn't call a new function). Each will be stuck until a recursive call it has made has completed.

Then the whole lot unwinds, each saying "middle" (except for 0) and "BYE", then allowing the preceding functions to get going again in turn.

Here is @Chervil's brilliant diagram again, but I've taken the liberty of adding the parameter sent to the function at the start of each line.

5....................hello 
4................hello 
3............hello 
2........hello 
1....hello 
0hello 
0BYE
1....middle
1....BYE
2........middle
2........BYE
3............middle
3............BYE
4................middle
4................BYE
5....................middle
5....................BYE

As you can see, each function is stuck and can't continue until the function it called has finished.

I didn't fully follow your final question - there are no loops in your program, just an if statement, so nothing is going to get "run in its entirety again".

I don't know whether it helps, but when I'm struggling with recursive functions sometimes I like to think of each one with a different parameter as a completely different function. In this case buildWall1(), buildWall2(), buildWall3(), etc. I suspect that everyone has a different way of "seeing" how they work.

Have a browse through topics on this forum. Recursive functions seem to come up fairly regularly. (The classic would be the factorial function.)

[adam2016]

thanks that helped a lot I'm getting the hang of it now I wrote it out on a piece of paper and it started to make more sense just one final question

#include <iostream>

using namespace std;


int fact(int num){


    if(num == 1){

        return 1;

    }else{

      cout << "hi" << endl;
      return num*fact(num - 1);
    }

    cout << "bye" << endl;


}

in this code ^^ how come bye never gets printed,I thought BYE would get printed 4 times,does it not get printed because return prevents the rest of the code from running in other words ending the function?

[cire]

In all cases you return from the function before line 20 is reached. You return on either line 12 or line 17, which both precede line 20. (I would not be surprised if your compiler generates a warning about unreachable code.)