C recursion flow-CodePudding

Could someone explain why is this printing hashtags per line from 1 to h. Because from my understanding the function is calling itself before even the for loop and it shouldn't print at all. If I move function calling below the for loop then it prints from h to 1 per line.

void draw (int h)
{
    if(h == 0)
    {
        return;
    }
    draw(h - 1);
    for(int i = 0; i < h;   i)
    {
        std::cout << "#";
    }
    std::cout<<std::endl;
}

CodePudding user response：

When the function draw is called, its information (value of variables, code segment, etc) is pushed onto a stack. This stack grows more and more as you make your recursion calls. The stack for draw(5) for instance would be draw(5), draw(4), and so on with draw(5) being at the bottom of the recursion stack.

Now to avoid infinte recursion calls, your condition (h == 0) acts as a base case.

Once the base case is reached, the function draw(0) terminates and is popped off the top of the recursion stack. Now the prior procedures are then popped out of the stack in a LIFO (Last-In-First-Out) order and continue their execution which includes the for loop printouts.

For instance, the first printout would be a single #. This is due to the recursion call draw(1) being next on the stack after the base case draw(0) terminated. Remember that draw(1) still has the value of 1 for its parameter h, which leads to that single # printout. Once draw(1) is done with its execution draw(2) takes over which prints two # and so forth.

To visually see this recursion you could utilize more printouts in the draw function to give you an overview of the order of recursive calls, but I highly recommend getting familiar with using a debugger to step through your C code and clearly see the recursion.

CodePudding user response：

I have found that the "substitution method" is often clarifying.

Let's look at a smaller example, draw(2).

Replacing h with 2 in the function body gives

if(2 == 0)
{
    return;
}
draw(2 - 1);
for(int i = 0; i < 2;   i)
{
    std::cout << "#";
}
std::cout<<std::endl;

Since the first condition is false, we must do draw(1) before we can continue with the loop.
Substituting again gives

if(1 == 0)
{
    return;
}
draw(1 - 1);
for(int i = 0; i < 1;   i)
{
    std::cout << "#";
}
std::cout<<std::endl;

The first condition is still false, so we need draw(0):

if(0 == 0)
{
    return;
}
draw(0 - 1);
for(int i = 0; i < 0;   i)
{
    std::cout << "#";
}
std::cout<<std::endl;

Now the first condition is true, so we return without doing anything, and can continue with the loop in draw(1):

for(int i = 0; i < 1;   i)
{
    std::cout << "#";
}
std::cout<<std::endl;

which prints one character.
Then, we return to the loop in draw(2):

for(int i = 0; i < 2;   i)
{
    std::cout << "#";
}
std::cout<<std::endl;

which prints two characters, and we're done.

You could also aid your reasoning by replacing the recursion with dedicated functions:

void draw_0() {}
void draw_1() { draw_0(); std::cout << "#\n";}
void draw_2() { draw_1(); std::cout << "##\n";}
void draw_3() { draw_2(); std::cout << "###\n";}
void draw_4() { draw_3(); std::cout << "####\n";}
void draw_5() { draw_4(); std::cout << "#####\n";}

and then consider what happens with draw_5().