Recursion in C++

Since we can continue to apply the algorithm indefinitely, what is the base case? We will see that the base case is set arbitrarily as the number of times we want to divide the triangle into pieces. Sometimes we call this number the "degree" of the fractal. Each time we make a recursive call, we subtract 1 from the degree until we reach 0. When we reach a degree of 0, we stop making recursive calls. The code that generated the Sierpinski Triangle in Figure 3 is shown in ActiveCode 1.

xxxxxxxxxx

#include <CTurtle.hpp>

​

namespace ct = cturtle;

​

void draw_triangle(ct::Point a, ct::Point b, ct::Point c, ct::Color color, ct::Turtle& myTurtle){

    myTurtle.fillcolor(color);

    myTurtle.penup();

    myTurtle.goTo(a);

    myTurtle.pendown();

    myTurtle.begin_fill();

    myTurtle.goTo(c);

    myTurtle.goTo(b);

    myTurtle.goTo(a);

    myTurtle.end_fill();

}

​

//getMid already defined as "middle" function in C-Turtle namespace :)

​

void sierpinski(ct::Point a, ct::Point b, ct::Point c, int degree, ct::Turtle& myTurtle){

    const std::string colormap[] = {"blue", "red", "green", "white", "yellow", "violet", "orange"};

    draw_triangle(a,b,c, {colormap[degree]}, myTurtle);

    if(degree > 0){

        sierpinski(a, ct::middle(a, b), ct::middle(a, c), degree - 1, myTurtle);

        sierpinski(b, ct::middle(a, b), ct::middle(b, c), degree - 1, myTurtle);

xxxxxxxxxx

#Recursive example of the Sierpinski Triangle.

​

import turtle

​

def drawTriangle(points,color,myTurtle):

#Draws a triangle using the diven points and color.

    myTurtle.fillcolor(color)

    myTurtle.up()

    myTurtle.goto(points[0][0],points[0][1])

    myTurtle.down()

    myTurtle.begin_fill()

    myTurtle.goto(points[1][0],points[1][1])

    myTurtle.goto(points[2][0],points[2][1])

    myTurtle.goto(points[0][0],points[0][1])

    myTurtle.end_fill()

​

def getMid(p1,p2):

    return ( (p1[0]+p2[0]) / 2, (p1[1] + p2[1]) / 2)

​

def sierpinski(points,degree,myTurtle):

    colormap = ['blue','red','green','white','yellow',

                'violet','orange']

    drawTriangle(points,colormap[degree],myTurtle)

    if degree > 0:

The program in ActiveCode 1 follows the ideas outlined above. The first thing sierpinski does is draw the outer triangle. Next, there are three recursive calls, one for each of the new corner triangles we get when we connect the midpoints. Once again we make use of the standard turtle module that comes with Python. You can learn all the details of the methods available in the turtle module by using help('turtle') from the Python prompt.

Look at the code and think about the order in which the triangles will be drawn. While the exact order of the corners depends upon how the initial set is specified, let's assume that the corners are ordered lower left, top, lower right. Because of the way the sierpinski function calls itself, sierpinski works its way to the smallest allowed triangle in the lower-left corner, and then begins to fill out the rest of the triangles working back. Then it fills in the triangles in the top corner by working toward the smallest, topmost triangle. Finally, it fills in the lower-right corner, working its way toward the smallest triangle in the lower right.

Sometimes it is helpful to think of a recursive algorithm in terms of a diagram of function calls. Figure 4 shows that the recursive calls are always made going to the left. The active functions are outlined in black, and the inactive function calls are in gray. The farther you go toward the bottom of Figure 4, the smaller the triangles. The function finishes drawing one level at a time; once it is finished with the bottom left it moves to the bottom middle, and so on.

Figure 4: Building a Sierpinski Triangle

The sierpinski function relies heavily on the getMid function. getMid takes as arguments two endpoints and returns the point halfway between them. In addition, ActiveCode 1 has a function that draws a filled triangle using the begin_fill and end_fill turtle methods.

Visual Studio can be used to create similar turtle-like graphics in C++ using the provided class "Turtle.cpp". Visual Studio files can be opened together with the as a .sln file. Try downloading and running the following code from GitHub.

Look at the Turtle.cpp file. Try changing the code within the turtle's draw loop and using the predefined functions.