Home > Blockchain >  Need an explanation for how this specific recursion works
Need an explanation for how this specific recursion works

Time:10-21

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.

CodePudding user response:

It helps if you expand each call in line:

draw(4)
{
  draw(3)
  {
    draw(2)
    {
      draw(1)
      {
        draw(0) { nop }
        print 1 *
      }
      print 2 *
    }
    print 3 *
  }
  print 4 *
}

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

CodePudding user response:

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

CodePudding user response:

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);
  }
}
  • Related