How would you generate a Sierpinski Triangle in C (recursively)

Question

I'm wondering how I could generate a Sierpinski Triangle of a certain depth recursively in C.

I wrote this function to generate a triangle of height h made of * from the coordinates (x,y) of the top point.

void triangle(char display[100][100],int x, int y, int h) {
    
    for (int row = y; row<=h-1+y; row++) {
        for (int column = x; column<=2*(row+1-y)+x-2; column++) {
            display[row][column-(row+1-y)+1] = '*';
        }
    }
    
    for (int i = 0 ; i<100 ; i++) {
        for (int j = 0; j<100; j++) {
            if (display[i][j]=='\0')
                display[i][j]=' ';
        }
    }

    
    
}

Using this code I can generate "manually" the Sierpinski Triangle. but I'd like to do it recursively, for any depth and height ( with height divisible by 2^(depth)).

int main()
{
    char display[100][100] = { {0} };

    triangle(display, 20, 0, 5);
    
    triangle(display, 15, 5, 5);
    triangle(display, 25, 5, 5);
    
    triangle(display, 10, 10, 5);
    triangle(display, 30, 10, 5);
    
    triangle(display,  5, 15, 5);
    triangle(display, 15, 15, 5);
    triangle(display, 25, 15, 5);
    triangle(display, 35, 15, 5);
    

    for (int i=0 ; i<100; i++) {
        printf("\n");
        for (int j=0; j<100; j++) {
            printf("%c", display[i][j]);
        }
    }
}

This is my output for the code above:

Answer 1

This is not a Sierpinski triangle, just almost looks like one. You are drawing individual little triangles (as a side effect it has gaps between those triangles -> "...*** ***...".

The best way to imagine how you would create such a triangle is to grab a pencil and a paper (there are optimized versions of creating a triangle, but the mechanical approach is good for a start):

1. choose a depth (say: 3)
2. Draw a triangle (preferably equilateral but any can do)
3. (if depth = 0 then RETURN from here, otherwise continue)
4. decrease depth
5. Halve all sides and mark those points (for visual aid)
6. Connect these points so you will see 4 equal, smaller triangles
7. Select Smaller Triangle #1
8. Call line 3.
9. Select Smaller Triangle #2
10. Call line 3.
11. Select Smaller Triangle #3
12. Call line 3.
13. Select Smaller Triangle #4
14. Call line 3.

Somewhere in the process you need to manage the state of the depth which starts at a positive integer. "Call line 3" is usually a subroutine that saves state when entered, and restores that when returned from. You have to decrease Depth between recursive calls and check it if it is 0 and when you reach 0, you have to RETURN. It can be a global variable (easier to understood but ugly), or it can be an argument to the drawing function (nice).

This "select Smaller Triangle #x and Call line 3." is the self recursive call. Selecting a triangle is just calculating the proper coordinates of the smaller triangle from the larger triangle.

The recursive nature kicks in if the depth is more than 1. The code will check the depth (and return if reached 0), subdivide the original triangle, call itself on the first smaller triangle, effectively handling this smaller triangle as if it were the original large one (the function itself has no notion of "larger" and "smaller").