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

i'm wondering how generate sierpinski triangle of depth recursively in c.

i wrote function generate triangle of height h made of * coordinates (x,y) of top point.

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

using code can generate "manually" sierpinski triangle. i'd recursively, depth , height ( height divisible 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);       (int i=0 ; i<100; i++) {         printf("\n");         (int j=0; j<100; j++) {             printf("%c", display[i][j]);         }     } } 

this output code above:

this not sierpinski triangle, looks one. drawing individual little triangles (as side effect has gaps between triangles -> "...*** ***...".

the best way imagine how create such triangle grab pencil , paper (there optimized versions of creating triangle, mechanical approach start):

1. choose depth (say: 3)
2. draw triangle (preferably equilateral can do)
3. (if depth = 0 return here, otherwise continue)
4. decrease depth
5. halve sides , mark points (for visual aid)
6. connect these points see 4 equal, smaller triangles
7. choose smaller triangle #1
8. call line 3.
9. choose smaller triangle #2
10. call line 3.
11. choose smaller triangle #3
12. call line 3.
13. choose smaller triangle #4
14. call line 3.

somewhere in process need manage state of depth starts @ positive integer. have decrease between recursive calls , check if 0 , when reach 0, have return. can global variable (easier understood ugly), or can argument drawing function (nice).

this "choose smaller triangle #x , call line 3." self recursive call. choosing triangle calculating proper coordinates of smaller triangle larger triangle.

the recursive nature kicks in if depth more 1. code check depth (and return if reached 0), subdivide original triangle, call on first smaller triangle, handling smaller triangle if original large 1 (the function has no notion of "larger" , "smaller").