pythondsintro-VisualizingRecursion.ptx

<section xml:id="recursion_introduction-visualizing-recursion">
        <title>Introduction: Visualizing Recursion</title>
        <p>In the previous section we looked at some problems that were easy to
            solve using recursion; however, it can still be difficult to find a
            mental model or a way of visualizing what is happening in a recursive
            function. This can make recursion difficult for people to grasp. In this
            section we will look at a couple of examples of using recursion to draw
            some interesting pictures. As you watch these pictures take shape you
            will get some new insight into the recursive process that may be helpful
            in cementing your understanding of recursion.</p>
        <p>The conventional tool used for these kinds of illustrations is Python's turtle graphics
            module called <c>turtle</c>. The <c>turtle</c> module is standard with all
            versions of Python and is very easy to use. The metaphor is quite
            simple. You can create a turtle and the turtle can move forward,
            backward, turn left, turn right, etc. The turtle can have its tail up or
            down. When the turtle's tail is down and the turtle moves it draws a
            line as it moves. To increase the artistic value of the turtle you can
            change the width of the tail as well as the color of the ink the tail is
            dipped in.</p>
        <p>Here is a simple example to illustrate some turtle graphics basics. We
            will use the turtle module to draw a spiral recursively.
            <xref ref="lst-turt1-cpp"/> shows how it is done. After importing the <c>turtle</c>
            module we create a turtle. When the turtle is created it also creates a
            window for itself to draw in. Next we define the drawSpiral function.
            The base case for this simple function is when the length of the line we
            want to draw, as given by the <c>len</c> parameter, is reduced to zero or
            less. If the length of the line is longer than zero we instruct the
            turtle to go forward by <c>len</c> units and then turn right 90 degrees.
            The recursive step is when we call drawSpiral again with a reduced
            length.</p>
        <exploration xml:id="expl-lst-turt1-cpp">
            <title>Example of Turtle Graphics</title>
            <task xml:id="lst-turt1-cpp" label="lst-turt1-cpp">
                <title>C++ Implementation</title>
                <statement><program xml:id="lst_cturt1" interactive="activecode" language="cpp" label="lst_cturt1-prog"><input>
#include &lt;CTurtle.hpp&gt;
namespace ct = cturtle;

void spiral(ct::Turtle&amp; turtle, int length) {
    if (length &gt; 0) {
        turtle.forward(length);
        turtle.right(90);
        spiral(turtle, length - 5);
    }
}

int main() {
    ct::TurtleScreen screen;
    ct::Turtle turtle(screen);

    spiral(turtle, 100);

    screen.bye();
    return 0;
}
                </input></program></statement>
            </task>
            <task xml:id="lst-turt1-py" label="lst-turt1-py">
                <title>Python Implementation</title>
                <statement><program xml:id="lst_turt1" interactive="activecode" language="python" label="lst_turt1-prog"><input>
#Creates an inward spiral through recursion.

import turtle

def drawSpiral(myTurtle, lineLen):
    if lineLen &gt; 0:
        myTurtle.forward(lineLen)
        myTurtle.right(90)
        drawSpiral(myTurtle,lineLen-5) #function makes recursive call.

def main():
    myTurtle = turtle.Turtle()
    myWin = turtle.Screen()
    drawSpiral(myTurtle,100)
    myWin.exitonclick()

main()
                </input></program></statement>
            </task>
        </exploration>
        <p>That is really about all the turtle graphics you need to know in order
            to make some pretty impressive drawings. For our next program we are
            going to draw a fractal tree. Fractals come from a branch of
            mathematics, and have much in common with recursion. The definition of a
            fractal is that when you look at it the fractal has the same basic shape
            no matter how much you magnify it. Some examples from nature are the
            coastlines of continents, snowflakes, mountains, and even trees or
            shrubs. The fractal nature of many of these natural phenomenon makes it
            possible for programmers to generate very realistic looking scenery for
            computer generated movies. In our next example we will generate a
            fractal tree.</p>
        <p>To understand how this is going to work it is helpful to think of how we
            might describe a tree using a fractal vocabulary. Remember that we said
            above that a fractal is something that looks the same at all different
            levels of magnification. If we translate this to trees and shrubs we
            might say that even a small twig has the same shape and characteristics
            as a whole tree. Using this idea we could say that a <em>tree</em> is a trunk,
            with a smaller <em>tree</em> going off to the right and another smaller <em>tree</em>
            going off to the left. If you think of this definition recursively it
            means that we will apply the recursive definition of a tree to both of
            the smaller left and right trees.</p>
        <p>Let's translate this idea to some C++ code. <xref ref="lst-fractree-py"/>
            shows how we can use Python with our turtle to generate a fractal tree. Let's look at
            the code a bit more closely. You will see that on lines 5 and 7 we are
            making a recursive call. On line 5 we make the recursive call right
            after the turtle turns to the right by 20 degrees; this is the right
            tree mentioned above. Then in line 7 the turtle makes another recursive
            call, but this time after turning left by 40 degrees. The reason the
            turtle must turn left by 40 degrees is that it needs to undo the
            original 20 degree turn to the right and then do an additional 20 degree
            turn to the left in order to draw the left tree. Also notice that each
            time we make a recursive call to <c>tree</c> we subtract some amount from
            the <c>branchLen</c> parameter; this is to make sure that the recursive
            trees get smaller and smaller. You should also recognize the initial
            <c>if</c> statement on line 2 as a check for the base case of <c>branchLen</c>
            getting too small. The C++ equivalent to this function is shown below and exists in <q>Turtle.cpp</q>.</p>

        <listing xml:id="lst-fractree-py" names="lst_fractree">
            <caption>Fractal Tree</caption>
            <program language="python" label="lst-fractree-py-prog"><input>
def tree(branchLen,t):
    if branchLen &gt; 5:
        t.forward(branchLen)
        t.right(20)
        tree(branchLen-15,t)
        t.left(40)
        tree(branchLen-10,t)
        t.right(20)
        t.backward(branchLen)
            </input></program>
        </listing>
        <p>The complete program for this tree example is shown in <xref ref="lst-complete-tree-cpp"/>.  Before you run
            the code think about how you expect to see the tree take shape. Look at
            the recursive calls and think about how this tree will unfold. Will it
            be drawn symmetrically with the right and left halves of the tree taking
            shape simultaneously? Will it be drawn right side first then left side?</p>
        <exploration xml:id="expl-lst-complete-tree-cpp">
            <title>Complete Tree Code</title>
            <task xml:id="lst-complete-tree-cpp" label="lst-complete-tree-cpp">
                <title>C++ Implementation</title>
                <statement><program xml:id="lst_complete_ctree" interactive="activecode" language="cpp" label="lst_complete_ctree-prog"><input>
#include &lt;CTurtle.hpp&gt;

namespace ct = cturtle;

void tree(ct::Turtle&amp; turtle, int length) {
    if(length &gt; 5){
        turtle.forward(length);
        turtle.right(20);
        tree(turtle, length - 15);
        turtle.left(40);
        tree(turtle, length - 15);
        turtle.right(20);
        turtle.back(length);
    }
}

int main() {
    ct::TurtleScreen screen;
    screen.tracer(3);//Draw faster.
    ct::Turtle turtle(screen);
    turtle.pencolor({"green"});

    //Make the trees "grow" upwards
    turtle.left(90);

    //Start growing from further down.
    turtle.penup();
    turtle.backward(100);
    turtle.pendown();

    //Draw the tree.
    tree(turtle, 75);

    screen.bye();
    return 0;
}
                </input></program></statement>
            </task>
            <task xml:id="lst-complete-tree-py" label="lst-complete-tree-py">
                <title>Python Implementation</title>
                    <statement><program xml:id="lst_complete_tree" interactive="activecode" language="python" label="lst_complete_tree-prog"><input>
#Creates a tree by using recursion.

import turtle

def tree(branchLen,t):
    if branchLen &gt; 5:
        t.forward(branchLen) #Turtle goes forward.
        t.right(20)
        tree(branchLen-15,t) #Recursive call
        t.left(40)
        tree(branchLen-15,t) #Recursive call
        t.right(20)
        t.backward(branchLen) #Turtle must go back the same distance
                #as it went forward to draw the tree
            #evenly.

def main():
    t = turtle.Turtle()
    myWin = turtle.Screen()
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("green")
    tree(75,t)
    myWin.exitonclick()

main()
                </input></program></statement>
            </task>
        </exploration>
        <p>Notice how each branch point on the tree corresponds to a recursive
            call, and notice how the tree is drawn to the right all the way down to
            its shortest twig. You can see this in <xref ref="fig-tree1"/>. Now, notice
            how the program works its way back up the trunk until the entire right
            side of the tree is drawn. You can see the right half of the tree in
            <xref ref="fig-tree2"/>. Then the left side of the tree is drawn, but not by
            going as far out to the left as possible. Rather, once again the entire
            right side of the left tree is drawn until we finally make our way out
            to the smallest twig on the left.</p>
        
        <figure align="center" xml:id="fig-tree1">
            <caption>The Beginning of a Fractal Tree.</caption>
                <image source="Recursion/tree1.png" width="50%">
                <description><p>Screenshot of a computer window titled 'Python Turtle Graphics' showing the initial stage of a fractal tree drawing. The window displays a simple black curve on a white background, representing the trunk of the tree starting to branch off. This image captures the first step in a programming exercise to draw a complex fractal tree using recursive functions.</p></description>
                </image>
            </figure>

        <figure align="center" xml:id="fig-tree2">
            <caption>The First Half of the Tree.</caption>
                <image source="Recursion/tree2.png" width="50%">
                <description><p>Screenshot of a computer window with the title 'Python Turtle Graphics', depicting a partially completed fractal tree drawing. The graphic shows a black tree with a simple trunk that splits into several branching limbs and smaller branches, all rendered on a white background. The image visually represents the midpoint of a recursive drawing process in programming, with the tree structure becoming increasingly complex towards the top.</p></description>
                </image>
            </figure>


        <p>This simple tree program is just a starting point for you, and you will
            notice that the tree does not look particularly realistic because nature
            is just not as symmetric as a computer program. The exercises at the end
            of the chapter will give you some ideas for how to explore some
            interesting options to make your tree look more realistic.</p>
  <reading-questions xml:id="rq-visualizing-recursion">
            <p>Modify the recursive tree program using one or all of the following
                ideas:</p>
            <p><ul>
                <li>
                    <p>Find the HDC-related operations to modify the thickness of the branches so that as the <c>branchLen</c>
                        gets smaller, the line gets thinner.</p>
                </li>
                <li>
                    <p>Modify the color of the branches so that as the <c>branchLen</c> gets
                        very short it is colored like a leaf.</p>
                </li>
                <li>
                    <p>Modify the angle used in turning the turtle so that at each branch
                        point the angle is selected at random in some range. For example
                        choose the angle between 15 and 45 degrees. Play around to see
                        what looks good.</p>
                </li>
                <li>
                    <p>Modify the <c>branchLen</c> recursively so that instead of always
                        subtracting the same amount you subtract a random amount in some
                        range.</p>
                </li>
            </ul></p>

    <program xml:id="recursion_sc_3" interactive="activecode" language="cpp" label="recursion_sc_3-prog">
        <input>


        </input>
    </program>
</reading-questions>  
<conclusion><p>
    <!-- extra space before the progress bar -->            
</p></conclusion>
    </section>