Star printing in C the hard way

Question

I've started exercising some C and found this nice exercise where I have to print a triangle via input. for the input 6 it will print

*
**
***
****
*****
******
*****
****
***
**
*

Now, looking at it I thought, well, that's not such a hard task. So I decided to try and write it using recursion, no loops and only 2 variables. the function should looks like this:

void PrintTriangle(int iMainNumber, int iCurrNumber)
{
   //Logic goes here
}

A few hours later I realized this is a lot harder than I thought, since I need to pass enough information for the function to be able to "remember" how much triangles it should print.

So now I decided to ask you if that is even possible.

(remember, no loops, no other functions, only recursion).

EDIT: This isn't homework, this is out of sheer curiosity. However I probably can't validate for you. I've managed to get halfway through with this

void PrintTriangle(int iMainNumber, int iCurrNumber)
{
    if (iMainNumber == 0)
    {
        printf("\r\n");
    }
    else if (iMainNumber == iCurrNumber)
    {
        printf("\r\n");
        PrintTriangle(iMainNumber - 1, 0);
    }
    else
    {
        printf("%s", MYCHAR);
        PrintTriangle(iMainNumber, iCurrNumber + 1);
    }
}

I got stuck trying to create the opposite function, I believe that if I could do it, I would be able to use the fact that iMainNumber and iCurrNumber are positive or negative to navigate through the functions flow.

In other words, when the parameters are negative I would print a descending star in the length of the input minus one, and when the parameters are positive I would print the ascending star in the length of the input.

I've thought about Using a flag, but not instead of 2 integers.

Maybe if I'd add another flag and have 2 integers and a flag then I could solve it, but as I said, I tried to limit myself to 2 integers.

What I'm starting to think is that there is no way to pass the information required to print an ascending star in this method without using more than 2 integers and recursion.

But I'm still not so sure about that, hence the question.

Answer 1

I came up with:

void PrintTriangle(int size, int indent)
{
    switch(size) {
    case 0:
        if (indent > 1) PrintTriangle(size, indent-1);
        putchar('*');
        break;
    case 1:
        PrintTriangle(size-1, indent+1);
        putchar('\n');
        break;
    default:
        PrintTriangle(1, indent);
        PrintTriangle(size-1, indent+1);
        PrintTriangle(1, indent);
        break; }
}

int main()
{
    PrintTriangle(6, 0);
    return 0;
}

as a quick first attempt. Seems to do the job.

size is the size of the triangle to print, and indent is the number of extra stars to print before each row of the triangle. size==0 means just print indent stars and no newline (used to print the indent before the triangle)

If you want something a bit more compact, you could rewrite this as:

void PrintTriangle(int size, int indent)
{
    if (size <= 0) {
        if (indent > 1) PrintTriangle(size, indent-1);
        putchar('*');
    } else {
        if (size > 1) PrintTriangle(1, indent);
        PrintTriangle(size-1, indent+1);
        if (size > 1) PrintTriangle(1, indent);
        else putchar('\n'); }
}

Answer 2

Anything done with loops can be done with recursion with the same number of variables. You just have to tease out what is the state, and pass that updated state in a recursive call, instead of looping.

So let's do it iterativey, first. The input is size, the size of the triangle. Let's have two state variables, lineNumber from 1 to size*2-1 and columnNumber from 1 to size. Note that:

columnsForLine = lineNumber <= size ? lineNumber : size*2 - lineNumber

The iterative version would be like this:

int lineNumber = 1;
int columnNumber = 1;
int size = 6;
while (lineNumber <= size*2-1) {        
    printf("*");
    int columnsForLine = lineNumber <= size ? lineNumber : size*2 - lineNumber;
    if (columnNumber == columnsForLine) {
        printf("\n");
        columnNumber = 1;
        lineNumber += 1; 
    }
    else {
        columnNumber += 1;
    }
}

That does indeed work. Now how to do it recursively? Just tease out where state is being updated and do that as a recursive call:

void recstars(int size, int lineNumber, int columnNumber) {
    if (!(lineNumber <= size*2 - 1)) {
        return;
    }
    printf("*");
    int columnsForLine = lineNumber <= size ? lineNumber : size*2 - lineNumber;
    if (columnNumber == columnsForLine) {
        printf("\n");
        recstars(size, lineNumber + 1, 1);
    }
    else {
        recstars(size, lineNumber, columnNumber + 1);
    }
}
recstars(6, 1, 1);

And voila. Works for any size, e.g. 13.

Note that the code is basically the same, it's just a matter of doing the control flow differently. Also note that this is tail-recursive, meaning a smart compiler would be able to execute the recursive calls without growing the stack for each call.

---

Hmm if you only want to use 2 variables though, including the input, will be a bit trickier... you can always cheat and stuff all 3 integers into one integer, then unpack it & re-pack it each time. e.g.

void recstars(int state) {
    int size = state / 10000;
    int lineNumber = (state - size*10000) / 100;
    int columnNumber = state - size*10000 - lineNumber*100;
    if (!(lineNumber <= size*2 - 1)) {
        return;
    }
    printf("*");
    int columnsForLine = lineNumber <= size ? lineNumber : size*2 - lineNumber;
    if (columnNumber == columnsForLine) {
        printf("\n");
        recstars(size*10000 + (lineNumber+1)*100 + 1);
    }
    else {
        recstars(size*10000 + lineNumber*100 + (columnNumber+1));
    }
}
recstars(6*10000 + 1*100 + 1);

Seems to work. Is that legit, you think?

Otherwise, the tricky part isn't the recursion, it's just getting the job done with only 2 ints for state. Can you do it iteratively with only 2 integers?