Lesson 4 - Recursion

Overview

  1. Introduction to Lesson 4
  2. An Algorithmic Strategy: Recursion
  3. Three examples of recursion:
    1. Russian Nesting Dolls
    2. Computer Processes: wget and rm

An Introduction to Computational Thinking, Lesson 4

In Lesson 1 of this series introduced the idea of Computational Thinking, and talked about what an algorithm is.

In Lesson 2 we looked at four tenets of Computational Thinking.

Four Aspects of Computational Thinking

  • Problem Decomposition
    Breaking down data, processes, or problems into smaller, more manageable parts
  • Pattern Recognition
    Observing and recognizing patterns or trends in data
  • Abstraction/Model
    Identifying the general rules or principles that are responsible for those patterns or trends
  • Algorithm Design
    Developing instructions or procedures that can be used to solve this problem and others like it

In Lesson 3 we explored the development and use of algorithms.

Definition: Algorithm

An algorithm is a series of steps used to solve a problem, particularly steps that can be adapted for use in a computer program.

In this final lesson, Lesson 4, we're going to examine a specific algorithmic strategy called recursion.

An Algorithmic Strategy: Recursion

The last part of this series is going to focus on one particular way of solving problems certainly can be mathematical, but also has a creative, artistic aspect to it. Whether you appreciate this topic mathematically, creatively, artistically, or as a computer algorithm, I think you're going to enjoy it. We're going to talk about recursion.

Definition: Recursion

Recursion occurs when a process or an object refers to itself in such a way that the process or object is repeated.

Computers are very good at at repeating things, and one common way of doing this is using iteration, or a loop, to do the same thing over and over again. Recursion also involves repeating things, but with a twist: recursion requires that the thing repeat by referring to itself.

Example: Drawing Hands, by M.C. Escher

A simple example of something that is almost recursion is this drawing of Drawing Hands, a work by the Dutch graphic artist M.C. Escher (1898-1972). In this piece, a picture of a hand is drawing a picture of a hand, which in turn is drawing the picture of the first hand. The piece can be considered recursive in that the drawings of the hands refer to themselves.

(Why is this almost recursion?)

An important aspect of recursion is the fact that this self-referral can't continue infinitely. There has to be a way for the self-referencing to eventually come to a stop. In this example, the Drawing Hands continue to draw each other, and never stop referring to each other. This type of repetition is more correctly called a Strange Loop.

Russian Nesting Dolls

Learn about another example of visual recursion in this video.

Computer Processes: wget and rm

Actual real life recursive processes aren't difficult to find on the computer. Take a look at this video for two examples.

Assignment: Recursion

Now that you know a little about recursion, create your own example of a recursive object or process.

Assignment: Create a Recursion

  1. Create an original image that's recursive—a photograph you've taken, a drawing you made, an image you've created on the computer, a video that you've recorded—and upload it to a new VoiceThread. As part of the VoiceThread, explain how you created the recursion, and how your example illustrates recursion.
  2. Embed your VoiceThread in a blogpost. Write 1-3 sentences that describe what recursion is and introduce the VoiceThread example of recursion.