Recursion is the process of progressively reducing a problem into easier to solve versions of itself.

Recursion is a core concept in computer science, used to solve all kinds of challenges, from efficiently sorting lists to drawing the branches of a tree. It is about breaking large problems into a sequence of progressively smaller ones, until you reach one that you can solve.

This lesson is brief and should take ~10 minutes to complete.

You may recognize this as a *fractal*, a repeating pattern that displays a version of itself at any scale.
Fractals like the Sierpinski triangle can be repeated infinitely, each piece a part of a conceptually larger whole.

The Sierpinski triangle is an equilateral triangle that is subdivided *recursively* into smaller equilateral triangles. Equilateral meaning that all three sides of the triangle are of the same length.

You could continue to draw this shape by continuing in larger, or smaller scales.

Thinking about how we might explain how to draw a Sierpinski triangle to someone, we might say something like:

- draw a triangle of equal sides, then...
- divide that triangle into four smaller ones, then...
- divide each of those smaller triangles into yet four more triangles, then...
- divide each of THOSE smaller triangles into yet four more triangles….etc.

In that sequence, it’s only the first step that stands out from the subsequent ones. Either we’re telling the person to draw a triangle, or we’re telling them to divide a triangle. Each step requires more dividing than the step before it, and it isn’t really practical to do follow this sequences more than a handful of levels “deep”.

Recursion is a reflection of this kind of explanation, just a little flipped around.

With our Sierpinski triangle instructions, we could also go the other direction. Instead of starting by drawing a triangle, we could decide how “deep” we want to go. That is, how many sets of smaller and smaller triangles we want to draw. We could look at our paper and work our way up, drawing the smallest triangles first, following by the larger ones in sequence, until we’ve completed the process.

Regardless of if we’re moving in this sort of “down” or “up” way, we end up with the correct drawing. We can start with the largest, smallest set of the triangles, or we can start with the singular largest triangle. Either way we want to think about it, we end up with a Sierpinski triangle. It’s just a matter of how we broke up the problem.

Recursion is the process of progressively reducing a problem into easier to solve versions of itself.

With our Sierpinski triangle and a blank page, the problem is at it’s largest. We might have to create tens, hundreds, or even thousands of triangles, depending on how deep we want to go. But because we know the rules of this triangle, this is doable, even if it’s incredibly tedious. *Recursively*, we could say we’re solving the problem by thinking of smaller versions of the problem. We don’t have to know where every triangle goes on first glance at the page, because we can progressively work through each layer, division of triangle after division of triangle, adding smaller and smaller shapes.

Recursion as a computational problem solving technique is directly related to this kind of process. It is splitting the problem into a thousand smaller ones, until the only step that remains is to draw a triangle…then take a step back and draw another one, again, and again, and again. Larger, and larger.

Recursion is looking for the base, the core of the problem, by splitting all the problems leading up to it. It is seeing the largest triangle, splitting it into smaller triangles, and splitting those over and over until there’s no more splitting to be done. Once there, we run backwards, filling in the larger problems, the larger triangles, with the smaller ones that came before them.

That step of running "backwards" is probably a little different than what we did in our heads. The truly recursive version of drawing the Sierpinski triangle did not do *anything* until it broke the problem all the way down to what is, for us, usually the last step: drawing the smallest triangle in our set.

But conceptually, that's all recursion is. Solving a problem by solving the smallest problems, and moving *backwards* up the chain. We can add more technical words, like "base case" or "self-same sets", but fundamentally all the concepts are here.

**Now just a few questions...**

Let's take the real world 'operation' of cutting up a pizza. You've taken the pizza out of the oven and in order to serve it up you have to cut it in half, then cut those halves in half, then again cut those resultant halves in half. The operation of cutting the pizza you performing again and again until you've got the result you want (the number of slices). And for arguments sake let's say that an uncut pizza is a slice itself.

You're contribution is very appreciated.