Recursively count number of triangles in Sierpinski triangle

user_5070885 0
Viewed 51

I have this function that returns the number of triangles in a Sierpinski triangle based on the order.
I need to calculate it by summing the amounts from the recursive calls.
I'm not able to use static variables, modify the function parameters, or use global variables.
I tried using int count but I know that won't necessarily work because it'll be reset during the call.

int drawSierpinskiTriangle(GWindow& window, GPoint one, GPoint two, GPoint three, int order) {

    if (order == 0) fillBlackTriangle(window, one, two, three); // order 0 triangle

    // one is left point, two is right point, three is top point
    else {
        int count = 0;
        GPoint bottom = { (one.x + two.x)/ 2, (one.y + two.y)/ 2 }; // bottom side of triangle
        GPoint right = { (two.x + three.x)/ 2, (two.y + three.y)/ 2 }; // right  side of triangle
        GPoint left = { (one.x + three.x)/ 2, (one.y + three.y)/ 2 }; // left  side of triangle

        drawSierpinskiTriangle(window, one, left, bottom, order - 1);
        drawSierpinskiTriangle(window, two, right, bottom, order - 1);
        drawSierpinskiTriangle(window, three, left, right, order - 1);

        count++;

        return count;
    }
    return 0;
}
recursion c++
1 Answers

Your current implementation of drawSierpinskiTriangle will only return 0 or 1:
0 if order == 0,
or:
1 otherwise (because count is initialized to 0 and you use count++ once after all the recursive calls).

Instead of using count++, you should accumulate the result from the recursive calls:

count += drawSierpinskiTriangle(window, one, left, bottom, order - 1);
count += drawSierpinskiTriangle(window, two, right, bottom, order - 1);
count += drawSierpinskiTriangle(window, three, left, right, order - 1);

In addition you should return 1 when the recursion reaches the end (otherwise you will only accumulate zeroes):

if (order == 0)
{
    fillBlackTriangle(window, one, two, three); // order 0 triangle
    return 1;
}
user_185199210
Related