SLOG Post #5 - Summary of Recursion

What is Recursion?

According to "How to Think Like a Computer Scientist", recursive code is code that is defined in terms of itself. In practice, this means a function that calls itself within its own function body. While this style of programming may not be easy to grasp initially, it has many advantages and unique characteristics that make it a good skill to have.

Recursion is useful because you can write code that can solve complicated problems
as long as it works in a few key, simple scenarios. Essentially, you can create a simple function that repeatedly calls itself to break down the task into a series of short identical steps, without having to know or keep track of how many times the function has been called.

Examples of Recursion

A good example of the applications of recursion are fractals, which are shapes that can be created using recursive instructions. The Koch fractal is a particular fractal that has the appearance of "budding" triangles. Koch fractals have different orders: zeroth order is just a straight line; first order is like zeroth order with a triangular peak in the middle; second order is like the first order, except each line segment of the first has a triangular peak in the middle; and so on and so forth. Here is an image of the "evolution" of a Koch fractal (note: in this diagram, iteration has the same meaning as order):





Sometimes fractals can get a bit out of hand. Here is an image of a Koch "snowflake" fractal:



The amazing part about Koch fractals is that they only need a few lines of code to generate! It's almost unbelievable that such complicated shapes could be generated with such simple, repetitive instructions. This is the true beauty of recursion. Here's the code for the linear Koch fractal:

def koch(t, order, size):
    if order == 0:
        t.forward(size)
    else:
        for angle in [60, -120, 60, 0]:
           koch(t, order-1, size/3)
           t.left(angle)

(from "How to Think Like a Computer Scientist", http://openbookproject.net/thinkcs/python/english3e/recursion.html)

Recursion is also particularly useful for sifting through complicated arrays, such as arbitraily nested lists, and for working with recursive series, such as the Fibonnacci series. In fact, you can apply recursion to a great deal of problems, as long as you make sure that you understand how it works for each problem (ie. you should be able to trace it!)

Tracing Recursive Functions

In the CSC148 labs periods, we have been developing two main recursion-related skills: tracing recursive code, and writing code for simple recursive functions. I quite enjoyed learning about tracing. In CSC108, I would often take shortcuts in practice problems that required us to trace the entire function call simply because I was being lazy, but for recursive function tracing, I was actually encouraged to do so! When we traced in our labs, we learned that it's not necessary to show steps that have already been demonstrated to work in similar scenarios. For example, one of the functions that we traced was a function that finds the maximum degree of nesting in a list. Once we had traced the function call on a list of first degree nesting, we didn't have to trace that process again when the function was called on a list of second degree nesting. We traced this way to reinforce the idea that you can trust a function to work in complex tasks if those tasks are a composition of many smaller, simpler tasks that you know the function can work with.

Writing Recursive Code

After tracing, we moved on to writing recursive code. I'll admit that initially, writing our own recursive functions was a little difficult. After looking at many examples and trying out a few questions, I soon discovered that there are some things that you should avoid when writing recursive functions. For example, you shouldn't accumulate data in a variable within the function body (ie. a counter) because the information stored in that variable is lost every time you call the function! Instead, you can put that variable as one of the arguments of the function, so that it isn't lost. I also learned that it's generally a good idea to start off by defining your base case and then figuring out how to solve the simplest example that isn't your base case. For example, if you are writing a recursive function for a Tree, your base case will probably be a Tree of depth 1, and the next simplest case would be a Tree of depth 2. If your code works for a Tree of depth 2, it can probably work for Trees of arbitrarily large depths. In this way, writing recursive functions is similar to writing test cases: you need to choose the cases that matter, all others are superfluous.

The Verdict

Recursion has been my favourite topic in CSC148 so far this year. I really like how recursive functions can be so concise, and I think that they're going to be a very useful addition to my toolbox of programming skills.