Recursive Turtle Tree

I know the title of this post may sound like random words thrown together, but it's actually a really cool activity to learn about recursion using the turtle module in Python (Linux users need to install tkinter). I've been learning about algorithms and abstract data structures as part of my faking a CS degree personal mission. Problem Solving with Algorithms and Data Structures has been a fantastic resource so far (and free). Although the authors' explanation of recursion is the best I've ever seen, I think I could just add a little to the tree drawing example. Here's the program they provide:

import turtle

def tree(branchLen,t):
    if branchLen > 5:
        t.forward(branchLen)
        t.right(20)
        tree(branchLen-15,t)
        t.left(40)
        tree(branchLen-15,t)
        t.right(20)
        t.backward(branchLen)

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()

Now I'm going to focus on the tree function. Notice tree calls itself twice. Now to step through how this function works, I am going to give each line a number and each recursive call a number such that 1.2 is the second time the first recursive call has been made and 2.3 is the third time the second call has been made. 

def tree(branchLen,t):
0    if branchLen > 5:
    1    t.forward(branchLen)
    2    t.right(20)
    3    tree(branchLen-15,t)     first recursive call
    4    t.left(40)
    5    tree(branchLen-15,t)    second recursive call
    6    t.right(20)
    7    t.backward(branchLen)

Let's trace branchLen = 30, following the code and what the turtle does. I've color coded each recursive call:

Code Line    Action                                Recursive Call
0               Passes > 5 test                       none
1               Forward 30                           none
2               Turns right 20 degrees           none
3               Calls tree(15)                        none
0               Passes > 5 test                      1.1
1               Forward 15                           1.1
2               Turns right 20 degrees            1.1
3               Calls tree(0)                           1.1
0               Fails > 5 test                          1.2
4               Turns Left 40 degrees             1.1
5               Calls tree(0)                           1.1
0               Fails > 5 test                          2.1
6               Turns right 20 degrees            1.1
7               Backward 15                         1.1
4               Turns Left 40 degrees             none
5               Calls tree(15)                         none
0               Passes > 5 test                        2.2
1               Forward 15                            2.2
2               Turns right 20 degrees             2.2
3               Calls tree(0)                            2.2
0               Fails > 5 test                           1.3               
4               Turns Left 40 degrees             2.2
5               Calls tree(0)                           2.2
0               Fails > 5 test                           2.3
6               Turns right 20 degrees            2.2
7               Backward 15                         2.2
6               Turns right 20 degrees            none
7               Backward 30                         none

If you choose a color such as red or orange, you can see how the function is executed in its entirety, but with interruptions. The colors that appear nested, such as orange inside the red, appear higher in the stack frame. They are completed first even though they started second, but the program continues to the red after the orange is completed. The next value of branchLen to create more recursive calls is 45. You could also try tracing tree(45), using tree(30) as a shortcut to emphasize the benefit of recursion.
               

Coursera -- Introduction to Interactive Programming in Python

A couple months ago, I took a free course on Coursera.com offered by Rice University and taught by Joe Warren, Scott Rixner, John Greiner, and Stephen Wong. Coursera offers the course a couple times a year, with 2014 offerings including March 24th and October 7th. The course is now part of the Fundamentals of Computing specialization and you earn a certificate after completion with the ability to earn additional "distinction" for scoring an A in the course (I did).

I recommend the course for anyone between "Isn't Python a snake?" to "Why should I use classes?" Students learn Python by developing simple games in CodeSkulptor, which includes a simple GUI like PyGame without using a terminal or setting up a coding environment. Homework includes quizzes over video material, building games in Python, and evaluating peers' code. I enjoyed the peer reviews because you can recognize common mistakes and see how other people solved the same problem you did. The game development approach finally helped me understand the point of object oriented programming. I went from fear of using classes, to empowered by building my own classes in the last three weeks of the course.

I am looking forward to the next course in the Fundamentals of Computing specialization, Principles of Computing. It is exciting to have an option for continuing to learn after a course. Us self-taught learners often waste time trying to decide what is the most appropriate and useful for us to learn next. If you can tolerate some corny Big Bang references and want to take your Python development to the level of using and understanding classes, you can enroll for free on Coursera.com