The Nonlinear Classroom

So, if you want to learn how to bring computational thinking skills for the 21st century into your classroom – perhaps you only vaguely remember the concept of recursion from a programming class you took in the early 2000s- this post is for you. 

---

Overview

From a pedagogical perspective, I like math problems featuring recursively built objects because the following is typically true: Numeracy gets tied to more abstract skills in algebra and geometry, and/or Students learn to use symmetry and pattern recognition as problem solving tools. 

If you are new to the idea of recursion in HS math, then I would encourage you to start with this problem in order to prime your mind for the concepts below.

An Informal Definition

Systems built recursively are built up piece by piece. Each piece builds off the previous piece according to a rule (often as a nice pattern, but not necessarily). The regularity of each of the individual pieces tends to have interesting consequences on the system as a whole – mathematical objects built recursively have symmetry. 

A good analogy is to Russian Dolls. Each doll fits inside the next according to a simple rule. The regularity of each doll gives the system as a whole (all of the dolls nested) a nice symmetry to it. This symmetry is what makes the Russian dolls a good children’s toy – A child is delighted each time their effort to get to the bottom of a stack of Russian dolls is thwarted by a new, scaled down version of the original doll.   Well.. ok in reality the child is delighted by throwing the pieces all over the room, and wouldn’t give the least bit of thought to the deep and beautiful idea of recursion. 

Moving on. Let’s look at some fundamental applications of recursive processes. 

---

Recursive Arithmetic

During a number talk, an elementary class is asked to compute 5 * 3. They add it up: 5 + 5 + 5 = 15. The teacher pushes further, “Great. Now what is 5 * 4?” In the early stages of learning, I imagine that some students will start all over, rotely applying the algorithm of repeated addition:  5 + 5+ 5 + 5 = 20. “Great.”, replies the sagacious teacher, “Can anyone solve it in a different way?” 

The student who moves from 5 * 3 to 5 * 4 in one step (by doing 15 + 5) has an implicit understanding of recursion even if they don’t know the word yet. 

Each number in the sequence 5, 10, 15, 20, 25, … fits inside the next like Russian dolls. Adding 5 is the rule to get from one doll to the next. 

Algorithms for 8 Year-Olds

Here’s how an algorithm developer would look at the two problem solving strategies: Starting the computation over by doing 5 + 5 + 5 + 5  wastes computational resources. It requires 3 additions.  On the other hand, if we already know that 5 * 3 = 15, it takes only one addition to compute 5 * 4. Just do 15 + 5.

This is how algorithm developers really think. They want to find the fastest algorithm to compute something, and this often requires estimating how many operations the computer will have to do. In this example, one problem solving strategy requires 1 addition, and a second strategy requires 3 additions.  So pick the cheaper option.

Well ok, it makes no difference how you compute this example since computers can do trillions of additions per second, but you can imagine more complex examples where the number of operations matter. 

Also, for the programmers out there, I am ignoring any discussion of the trade-off with memory because it is beyond the scope of this article and doesn’t change the main thrust of the narrative, that recursion is a fundamental computational and conceptual tool that one is forced to grapple with right from the start of mathematical learning.  

In fact, all of the basic arithmetic operations with whole numbers are built recursively:

• Repeatedly applying the operation of addition gives multiplication
• Repeatedly applying the operation of multiplication gives exponentiation
• Why stop there? Repeated exponentiation gives tetration.

---

Polynomial Recurrence Relations

In the previous example we saw recursion as the computational mechanism for doing arithmetic with whole numbers. E.g. The multiples of 5 can be generated recursively:  5, 10, 15, 20, 25, …It’s a short step to make the connection from arithmetic to algebra, and many teachers do just that – The number pattern above is a sample of points from the linear function y = 5x. Making this connection in the classroom is powerful pedagogy and lies right in the zone of proximal development as students abstract from concrete arithmetic to algebra. 

But, too often the connections to arithmetic are lost when students are introduced to quadratics, cubics, and the rest of the polynomials. Sure, polynomials have terms with powers, products, and sums, and that is basic arithmetic, but the connection to arithmetic feels tenuous in comparison to the tight connection between linear functions and patterns like 2, 7, 12, 17, 22,\ldots .  That is, until you view polynomials through the lens of recursion. 

Every polynomial function is defined by a recurrence relation.  Every polynomial can be Russian dolled, so to speak. Visual patterns give a great look at this idea. Take pattern number 6 for example:

How many toothpicks are there in the 100th iteration of this pattern? These are just Russian dolls made of toothpicks. Each shape fits in the next in a nice predictable pattern. This pattern happens to be a quadratic, and is modeled by the function y = \frac{3}{2} \cdot \left( x^2 + x \right). If you plug in the numbers x = 1, 2, 3, … you get out the number of toothpicks in each figure: y = 3, 9, 18, 30 … 

But wait, there’s more. Polynomials are actually defined in a recursive manner.  Yes. Using the recursive black magik one can summon polynomials from the ether.  And this has direct consequences on the properties of polynomials. How they behave. What they look like when you graph them, or represent them as visual patterns or number patterns. 

So look, my point isn’t that teachers don’t use visual patterns enough (although maybe we don’t), but what I’m really saying is that these nifty little patterns aren’t just one-off activities that you do in class for fun and forget about when it’s test time. The overarching idea here is recursion, it connects the algebra, geometry, and numerical behavior of polynomials. I believe we need to add that context to our classrooms. So much of the behavior of polynomials comes from their humble origin as the by-product of a recursive process. 

There isn’t enough space in this article to see how recursion manifests itself in the algebraic properties of polynomials, so please click here if you are interested in more resources on how to align your teaching of polynomial functions with recursive/computational thinking. 

---

Recursion to Build Symmetry

Applying a recursive process to build up shapes in 2 or 3 dimensions makes for some great visuals, especially via GIFs (I use ezgif to make free GIF animations in a pinch). GIFs are also great to use in a classroom as kids tend to like them and you can use the timing and repetition of the animation to pose fun questions in class (especially in counting questions where the animation goes too fast for students to count one by one for an answer). 

Because GIFS go one frame at a time to make an animation, they are the perfect file format to represent shapes or processes that build up in a step by step, recursive fashion. Take the toothpicks visual pattern from above, here it is again shown built up by recursion:

Notice that the object takes on more symmetry as the recursion progresses. This is no coincidence. Recursive processes almost can’t help but produce symmetric shapes. Let’s peek at a couple more examples.

Polynomials can be defined recursively, but so can exponential functions. The GIF below shows stages of constructing the Siepinski triangle fractal. The recursive rule says to remove the middle third of each solid green triangle. Iterate the recursive rule, and voila, you’ve produced a pretty shape that contains copies of itself at each scale (well in this case, up to degree 3, when the GIF loops to the start). Counting the number of green triangles (or the white ones, or both)  makes a great exercise for teaching exponential growth. Again, notice how the visual pattern, the numbers, and the algebra all show different aspects of the symmetry coming from a recursive process.    

Finally, I couldn’t write an article introducing recursion without at least paying lip service to the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, … this sequence is generated by a recursive rule: the next number comes from adding the previous two numbers. Everyone and their mother has written about these numbers. 

Just like the examples above, the recursively defined number pattern has symmetric geometric and algebraic counterparts. The Fibonacci spiral is a symmetric shape built from these numbers. Click here to read more about the Fibonacci spiral and golden ratio and how they appear in many naturally occurring symmetric structures, like the growth of flower petals. But hopefully at this point you are not too surprised by the appearance of symmetry. It’s just what recursion does. 

The narrative of this section started with fun visuals that are great for activities in class, but notice how we’ve found ourselves on the precipice of a much deeper idea – symmetry.

For now, I’m asking you to simply take me at my word that symmetry is an important idea in mathematics (the idea is formalized in a deep and beautiful area of math), and take the examples above as evidence that recursion can be used to build symmetry. 

---

You know where the weight room is? Practice Problems

Here are some problems and activities relating to recursion.

1. Can you show that every number in the recursively defined sequence 49, 4489, 444889, 44448889, … is a perfect square?

2. Can you show that no number in the recursively defined sequence 11, 111, 1111, 11111, … is a perfect square? click here

3. For a problem relating polynomial growth to recursion (guided discovery learning worksheet for students included) click here

4. For a problem combining geometry, polynomials, and recursive pizza cutting, click here. Worksheet for students included. 

---

Summary

You’ve made it this far –  Thanks for reading! Recursion is a deep idea. It shows up as a problem solving tool, a computational tool, and a systematic way to build mathematical objects. It can be used as an adjective, a noun, or a verb.  It runs through a ton of math and science, only a tiny amount of which is covered in this article.  

I always understand math ideas better when I see them applied in different areas. I hope that this article provided a context that you can take with you in your teaching. For more concrete resources – problems, student activities, links to extensions, see below. 

---

Learn more

One of my goals for this blog is to provide resources for teachers who want to learn more. Check out the topics below. Will you need these ideas in the day-to-day of teaching? It’s unlikely. But the more you know, the better you will be able to guide your aspiring STEM students, and field questions like, “When will I ever need this?”.

• When a computer scientist says recursion they mean a specific programming technique where a function repeatedly calls itself. It’s fundamental to the field of software engineering.  In fact, one of the first coding exercises that every single undergrad computer science student must complete is to write a computer program which computes the factorial of a number using recursion. 
• Mathematical induction is a method of proof built on recursion. In this instance, recursion is a problem solving tool – you don’t get an undergrad degree in math without solving at least a few problems by induction. It’s typically one of the first techniques a student learns in a course on logic and proofs. 
• Discrete time dynamical systems are used by engineers to model real world systems. These models are built via recursive rules which govern how the system changes from one point in time to the next. 
• In artificial intelligence, decision making is often done using recursive routines. See Reinforcement Learning, Dynamic Programming, and Bellman’s equation.
• I mentioned counting the number of operations an algorithm computes to run. This is called the time complexity. What I didn’t mention is the trade off with memory. To compute via recursion, the computer needs to store previous answers in memory. Depending on the application, storing things in memory can really slow down the computation, and actually be slower than re-computing the solution for each iteration. There is a trade-off between memory and time.