Need an explanation for how this specific recursion works

Question

I am currently learning recursion in c language. I encountered this when trying out some stuff

#include <stdio.h>

void draw(int x) 
{
  if (x > 0) 
  {
    draw(x-1);
    for (int i = 0; i < x; i++) 
    {
      printf("*");
    }
    printf("\n");
  }
}

int main (void) 
{
   draw(4);
}

I expected the code to print:

****
***
**
*

Instead, it prints:

*
**
***
****

Can anyone please explain why this is the case? Thank you.

re "paper and pencil" see [1](https://stackoverflow.com/a/11666815/849891), [2](https://stackoverflow.com/a/51285838/849891). — Will Ness, Oct 21 '22 at 16:59

Aconcagua · Answer 1 · 2022-10-20T13:01:57.390

It depends on when recursion occurs!

What happens in this code example is that the recursive call is done before you actually print a line:

draw(3)
    -> draw(2)
        -> draw(1)
            -> draw(0) // not doing anything
            -> print one asterisk
        -> print two asterisks
    -> print 3 asterisks

If you, in contrast, print first the asterisks and then call recursively:

for (int i = 0; i < x; i++) 
{
    printf("*");
}
printf("\n");

draw(x-1); // note: moved behind printing

then you get the result you originally expected.

Side note: printf("x") with just a single character contained in the string is pretty inefficient compared to using putchar('x') which effectively does the same (though admitted, you won't be noticing on running your programme).

score 2 · Answer 2 · edited Oct 21 '22 at 17:08

It helps if you expand each call in-line:

// draw(4) ==
{
  // draw(3) ==
  {
    // draw(2) ==
    {
      // draw(1) ==
      {
        // draw(0) ==
        { no-op } ;
        print 1 '*' ;
      } ;
      print 2 '*' ;
    } ;
    print 3 '*' ;
  } ;
  print 4 '*' ;
}

draw(4) first calls draw(3) and then it prints 4 '*'s.

But what does draw(3) do? It calls draw(2) and then it prints 3 '*'s and so on. So 3 '*'s are printed before 4 '*'s, and 2 '*'s are printed before 3 '*'s, and so on.

Vlad from Moscow · Answer 3 · 2022-10-20T12:54:12.807

In each call of the function it at first calls itself with the decreased by one value of x (provided that x is greater than 0)

void draw(int x) 
{
  if (x > 0) 
  {
    draw(x-1);
    //...

and only after that outputs the symbol '*' x times.

If you want to get the expected result then the function shall at first output the symbol '*' x times and after that call itself with the decreased by one value of x as for example

void draw(int x) 
{
  if (x > 0) 
  {
    for (int i = 0; i < x; i++) 
    {
      printf("*");
    }
    printf("\n");

    draw(x-1);
  }
}

Need an explanation for how this specific recursion works

3 Answers3