Computer Science
How To Use Recursion To Draw
A tutorial on recursion using processing.
In this article, I will describe what recursion is and how to use it to draw complex shapes. Before I go over this, I want to make sure the reader has a basic understanding of programming and processing. You don’t have to understand all the code; however, a basic understanding of programming and Javascript would be helpful.
Introduction to Recursion
Recursion is one of my favorite concepts from computing and mathematics. Formally the definition of recursion according to Merriam-Webster is.
2: the determination of a succession of elements (such as numbers or functions) by operation on one or more preceding elements according to a rule or formula involving a finite number of steps
3: a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first
However, my simpler definition is that recursion is the following “defining something in terms of itself in some way.” A similar concept to recursion is the Droste effect, where an image contains a smaller sub-image of the larger image. We see recursion in movies like Inception, where a dreamer dreams about dreaming, or in recursive artwork. Recursion can also be used to define infinite shapes like infinitely shrinking circles, rings, and tunnels.
Recursion exists in mathematics as a function defined in terms of itself. An example of a recursive function is the factorial function. This is often notated with an exclamation mark and is defined as the product of all the numbers from 1 to an integer N. We can define the factorial function recursively as the recurrence relation.
We can define N! = N(N-1)! then N! = N(N-1)(N-2)! and then N! = N(N-1)(N-2)(N-3)!
However, we have a problem. We can keep adding terms forever, and the equation will never stop. We can end up with 100 terms and still need to figure out what the value of N! is. This is called an infinite recursion or non-halting problem; also, in many programming languages, it’s called a StackOverflow error (That article is recursion itself).
We need a base case, a point where the recursion stops and doesn’t repeat. For the factorial function, this is when N = 0 and so 0! = 1, which stops the recursion. We also have a recursive case where the recursion continues with a progressively smaller or larger input. Usually the input to the function gets smaller each recursive call meaning we get the input closer to the base case. In our factorial function the input decreases by 1 each time.
A code example in Javascript would look like this.
function factorial(n) {
// base case when n = 0
if(n == 0) {
return 1;
}
return n * factorial(n-1);
}Another recursive function is the Fibonacci sequence defined by the Mathematician Fibonacci, who published it in his manuscript Liber Abaci. However, he was known by Indian mathematicians for centuries before him. The Fibonacci sequence is defined in terms of itself with two base cases at N = 1 and N = 2.
The first few terms of the sequence generated by this equation are 1, 2, 3, 5, 8, 13, and so on. The Fibonacci sequence and the associated golden ratio (Phi) have applications in mathematics, algorithms, design, architecture, and finance.
In Javascript the code would look like this.
function fib(n) {
// base case when n = 1 or 2
if(n == 1 || n == 2) {
return n;
}
return fib(n-1) + fib(n-2);
}In short, recursion is useful in many different areas and can be used to calculate interesting number sequences and some mathematical functions. However, what really makes it powerful is the ability to generate self-similarity at smaller scales. Often attributed to fractal geometry or other forms of geometry, these shapes are similar in shape but different in scale.
Recursion can also be used to generate smaller shapes in sequence and intricately complex shapes called finite subdivision rules. We will see how to use recursion to achieve exciting results next.
Applying Recursion in Graphics
The easiest way to see recursion’s usefulness is its application to graphics. We will use processing, a language based on Java used for generative art and computer graphics. Specifically, we will use the Javascript variant p5js. There are some interesting tutorials on processing if you want to learn it quickly, but I’ll jump in, assuming you understand the basics of programming. The only concepts you’ll really need are functions, mathematical operations, and conditional and looping statements.
Let’s start with a simple task to draw a series of circles one after the other, with each circle getting smaller and smaller by a factor of one-half and with a space between each circle. Our radius will shrink by 0.5 of the previous radius each time we draw a new circle. We can define an equation for a given radius of circle N by defining it as a function of the previous radius of circle N-1. Our first circle will have a radius of 200px and the second 100px, and so on.
In processing using p5js, the code to write this would look like the following.
// this function draws the circle at coordinates x and y with radius r.
function drawCircleRecursively(x, y, r) {
/* this is the base case where R(1) <= 2 we return nothing
because we want to stop the recursion. */
if(r <= 2) {
return;
}
// this draws the circle at x, y with radius r.
circle(x, y, r);
/* this is the recursive call which halves the radius
and increments x by r plus a margin to move to the right. */
drawCircleRecursively(x + r + 30, y, r/2);
}
function setup() {
createCanvas(1024, 768);
}
function draw() {
fill(0, 0, 255);
drawCircleRecursively(220, 384, 200);
}The recursive function is simple with a base case that checks in an if-statement if the radius ≤ 2 and then does nothing and returns if it is. The rest of the function draws the circle of radius r and then recursively calls the function again with the radius cut in half.
Let’s try again, but this time with another recursive type of drawing. Let’s draw a series of circles that rotate around a center point. The series of enclosing circles will be drawn towards the center of the screen. This initially will look like a series of spokes on a wheel. To do this, we need to know about polar coordinates. Polar coordinates are a coordinate system where instead of coordinates represented by lines on an XY grid, they are represented on a circle. With polar coordinates, we can represent circular paths more easily than with cartesian coordinates.
We will have one function to draw circles, the drawEnclosingCircles function, which is recursive and draws all the polar points in the circles array. It does this by converting them to cartesian coordinates and then calling the circle function to draw. The circles array contains a series of polar coordinates representing circle positions. We will have a createCircles function which uses a loop to create the polar coordinates in the circles array.
We can also add animation to it using dt; dt is a special variable based on the time between frames in milliseconds, times one over the framerate. We need dt because it represents the time between frames which allows for a smooth animation rather than an abrupt change if we didn’t use it. In the updateCircles function, the circle positions are updated based on dt and a small random amount. For each frame, the updateCircles function will be called, and the circle is moved a tiny amount.
When drawing, each draw call is called a frame and the number of frames per second is the frame rate. We can then find the time between draw calls to figure out how much the circle should have moved in that time. It’s like in physics, where we have a small amount of time dt in which an object travels. We use the same concept to animate the circles by using dt to add a small random amount to the angle of the circle. A color for each circle is calculated as a function of the power of the current r value for the circle.
class Point {
constructor(x, y) {
// constructor for a cartesian point with x and y
this.x = x;
this.y = y;
}
}
class Polar {
constructor(r, angle) {
// constructor for a polar coordinate with x and y
this.r = r;
this.angle = angle;
}
// this function transforms a point in polar coordinates to cartesian coordinates
toPoint() {
const x = this.r * cos(this.angle);
const y = this.r * sin(this.angle);
return new Point(x, y);
}
}
/**
* Creates a bunch of n circles starting from angle0 and r0.
*/
function createCircles(n, r0, angle0) {
const circles = [];
let r = r0;
let angle = angle0;
for(let i = 0; i < n; i++) {
// Create a new circle and then subtract from the radius a small random amount and add from the angle a small random amount
const p = new Polar(r, angle);
circles[i] = p;
r -= random(0.1, 5);
angle += random(QUARTER_PI, QUARTER_PI+0.01);
}
return circles;
}
/**
* This function updates the circles one by one by adding a small random angle to the circles position.
*/
function updateCircles(circles, dt) {
for(const p of circles) {
// update the circle's angle a small amount based on dt.
p.angle += random(PI/8, QUARTER_PI) * dt * 0.05;
}
}
let circles = [];
/**
* Draw each circle recursively using a recursive function passing in the index and array.
*/
function drawEnclosingCircles(circles, i) {
if(i >= circles.length) {
return;
}
// Convert the polar coordinate to cartesian to be drawn.
const p = circles[i].toPoint();
// Calculate a color using a fractional power law
const c = Math.pow(circles[i].r, 1.5) / 200;
fill(c * 30, 62, c * 80);
circle(p.x, p.y, 10);
// The recursive call which passes in the array and increments by 1.
drawEnclosingCircles(circles, i+1);
}
let dt, prevTime, nextTime;
const FPS = 60;
function setup() {
createCanvas(500, 500);
// create 100 circles
circles = createCircles(100, 200.0, 0.0);
prevTime = millis();
frameRate(FPS);
}
function draw() {
// calculate dt using time between frames and frames per second.
nextTime = millis();
dt = (nextTime - prevTime) * 1.0 / FPS;
prevTime = nextTime;
background(255);
// translate the sketch to middle of screen
translate(width/2, height/2);
drawEnclosingCircles(circles, 0);
updateCircles(circles, dt);
}We can see how the circles start off in a very well-ordered formation and then move off into chaos as the animation progresses. This almost looks like a galaxy or a cluster of particles moving in swirling water. Don’t worry if you don’t understand all the code; this was a complex example, and it takes some time to really understand it. The main point to focus on is the drawEnclosingCircles function which draws the circles from the array recursively. Focus on that function and read over it to make sure you understand it. In the next section, we’ll learn about the different types of recursion.
Types of Recursion
There are different varieties of recursion used. We’ve mostly used a standard type of recursive call called single recursion, where the recursive call can be anywhere in the function, and we only have one function, which calls itself. However, there are other types of recursive calls that can be used.
One type of recursion we haven’t used yet is mutual recursion. In mutual recursion, one function calls another, which calls that same function again.
This type of recursion can be used to draw more complex shapes than what we’ve been doing so far. Let’s say we want to draw a series of inscribed circles and squares. Inside a circle is an inscribed square, and inside a square is an inscribed circle.
We could have one function which draws the circle and another function which that draws a square. These will call each other recursively to draw a series of shapes inside each other. We can find the circle's radius by various methods, including the Pythagorean theorem. In short, our new radius will be calculated by multiplying our square side by the square root of 2. We will divide by 2 to find the new square’s side length.
The main two functions drawCircle recursively calls drawSquare which then calls drawCircle again until the side length is less than or equal to 1, at which point the recursion stops. This is our base case and ensures that we don’t recurse indefinitely and get a StackOverflow error.
function setup() {
createCanvas(windowWidth, windowHeight);
background(100);
rectMode(CENTER);
}
/**
* Draw square at x, y with side length s
*/
function drawSquare(s) {
// base case to stop recursion when side <= 1
if(s <= 1) {
return;
}
// set the color to red
stroke(255, 0, 0);
square(0, 0, s);
// recursively call drawCircle and multiply the side length by square root of 2
drawCircle(s * sqrt(2));
}
/**
* Draw circle at x, y with radius s/2, diameter s
*/
function drawCircle(s) {
const r = s / 2.0;
//set the color to blue
stroke(0, 0, 255);
circle(0, 0, r);
// recursively call drawSquare and halve the side length
drawSquare(s/2);
}
function draw() {
background(255);
// remove fill from shape
noFill();
// translate shape to center
translate(width/2, height/2);
// draw circle with diameter 500
drawCircle(500, 1);
}Another type of recursion is a sub-category of single recursion called tail recursion. In tail recursion, our recursive call is at the end of the function; this allows for the recursive function to be converted to a loop internally. In some programming languages like Haskell and Lisp, the compiler optimizes the function to make it run faster by converting it from a recursive function to an iteration. Our very first recursive drawing function, drawCircleRecursively, was tail recursive because the recursive call was at the very end of the function and didn’t have any other computations next to it.
To see an example of the difference between a function that is tail recursive versus a function that is not. Let’s create a function that adds the numbers from 1 to 10 using single recursion without tail recursion.
function addRec(n) {
// non tail recursive function
if (n == 10) {
return 10;
}
return n + addRec(n + 1);
}
let sum = addRec(1);
console.log(sum);Notice how each recursive call, the function has to add n to the current total, meaning after three calls, our sum will be n + (n + (n + (addRec(3))))
We can rewrite this using tail recursion by adding an extra sum parameter to store and pass the current sum and then just adding to that sum in the recursive call; that way, no extra computations are done next to the call.
function addRec(n, sum) {
// tail recursive function
if (n == 10) {
return n + sum;
}
return addRec(n + 1, sum + n);
}
let sum = addRec(1, 0);
console.log(sum);So far, our examples have used recursion in a very simple way to draw shapes that could have been drawn using a loop. In the next section, we will show how to use recursion to draw self-similar shapes that are very difficult to draw in a loop and easier to draw using recursion.
Self Similarity with Recursion
We can get more advanced and create self-similar shapes with recursion. Self-similarity means that the shape at different scales looks similar. If you zoom in on self-similar shapes, they will look similar, rather than if you hadn’t zoomed in at all. Fractals are self-similar; for example, coastlines look sort of similar if you zoom in, and so does the famous Mandelbrot set.
Recursion makes drawing self-similar shapes easy because we can use the same function at different scales to draw the same shape. To explore self-similarity, let’s draw a group series of squares in a square pattern several times recursively. To do this, we will pass in a scale parameter that goes from 0.0 to 1.0 and represents the scale as a fraction of the original shape size. The squares are drawn at intervals with N squares on each side inside each other.
We do N-squared recursive calls over all the loop iterations, which draws N*N squares each time the function is called. The new X is calculated by finding the column that the square should be in and adding a margin. The same is done for the new Y, except we use the row value. Then the draw function is recursively called.
function setup() {
createCanvas(640, 640);
}
// The number of squares on each side
const N = 2;
// The size of the largest square
const MAX_SIZE = 400;
// The factor by which we scale by in each recursive call
const SCALE_FACTOR = 2;
function selfSimilarSquares(x, y, scale) {
if(scale <= 0.001) {
return;
}
// We find the square size by multiplying the scale by the maximum square size
const size = scale * MAX_SIZE;
square(x, y, size);
// loop through N squared squares and draw each square
for(let i = 0; i < N*N; i++) {
const margin = size / Math.pow(N, 3);
// find the new x by finding i modulo N which represents the column and adding a margin
const xnew = x + (i % N) * size / N + margin;
// find the new x by finding i / N which represents the row and adding a margin
const ynew = y + Math.floor(i / N) * size / N + margin;
selfSimilarSquares(xnew, ynew, scale/Math.pow(N, SCALE_FACTOR));
}
}
function draw() {
translate(width/2-MAX_SIZE/1.5, height/2-MAX_SIZE/1.5);
selfSimilarSquares(0, 0, 1);
}We can see the self-similarity implicit in this shape when we zoom into one of the four squares. There’s also a two-fold symmetry along the X and Y axes. This means that along the X and Y axes, we can fold it in half and get the shapes to overlap.
Finite Subdivision Rules
Let’s look at another shape based on a finite subdivision rule. Finite subdivision rules are a method for diving up a shape by cutting it into smaller pieces based on specified rules. Each shape is recursively subdivided into more shapes based on a rule. Here are some examples of more complex rules. Each type of shape is called a tile type which is transformed into other tiles.
In this example, we will cut up a triangle into smaller triangles using a centroid rule. A centroid is the center of a shape found by calculating the arithmetic mean from each vertex. This is done using the midpoint formula. Where M is the midpoint and t represents each vertex of the triangle.
For an isosceles triangle, the centroid rule would look like the following drawing.
This rule is closely related to the barycentric subdivision rule, meaning the pattern will look very similar. We will subdivide the triangles on the unit square from [-1, 1] and then scale them and translate them to the center of the screen.
To store the triangles, we will use an Array (List) and use it to store a set of three vertices for each triangle. For each recursive call, we will generate a new list from the old list. This will generate three new triangles for each triangle in the list.
The main recursive function we have here is the subdivide function which takes in a new triangle and a recursion depth. The recursion depth defines how deep in the nested function calls we are. Then it finds the centroid using the midpoint formula by dividing each component by 3. Finally, it creates three new triangles with the centroid and returns the new list. This returns a deep array, so we flatten it, so it contains the right number of triangles.
In addition, N will represent our recursive depth, meaning how many recursive calls down we call for each recursive call. A higher N value generates more triangles.
To calculate the new color for each triangle, we can use the distance from (0, 0), which will be multiplied by some factor and added to our previous color. We can then find the modulo with 255, so the color doesn’t get larger than 255. This means we will end up with a colorful series of triangles.
The most complex function here is subdivide; however, all it is doing is just calculating the centroid and recursively generating new triangles from that centroid. Think of it as focusing on subdividing a single triangle until it gets to the recursive depth N.
let triangles = [[[0.0, 0.0], [-1.0, 1.0], [1.0, 1.0]]];
/**
* subdivide triangle t at depth n
*/
function subdivide(t, n) {
// base case when depth is 0
if(n <= 0) {
return t;
}
// find centroid (cx, cy) using midpoint formula
const cx = (t[0][0] + t[1][0] + t[2][0]) / 3.0;
const cy = (t[0][1] + t[1][1] + t[2][1]) / 3.0;
// centroid
const c = [cx, cy];
// calculate 3 triangles using centroid
const t0 = [t[0], c, t[1]];
const t1 = [t[1], c, t[2]];
const t2 = [t[0], c, t[2]];
// recurse for each triangle and decrement depth
const s0 = subdivide(t0, n-1);
const s1 = subdivide(t1, n-1);
const s2 = subdivide(t2, n-1);
return [s0, s1, s2];
}
// represents the recursive depth, higher number means more triangles
const N = 9;
function setup() {
createCanvas(windowWidth, windowHeight);
background(0);
fill(255);
rectMode(CENTER);
strokeWeight(0);
// subdivide and flatten to N-1 depth
triangles = subdivide(triangles[0], N).flat(N-1);
}
const SCALE = 500.0;
/**
* draw each triangle in the array
*/
function drawTriangles() {
let currColor = [120, 20, 180];
triangles.forEach(t => {
// find centroid from each triangle
const cx = (t[0][0] + t[1][0] + t[2][0]) / 3.0;
const cy = (t[0][1] + t[1][1] + t[2][1]) / 3.0;
// centroid
const c = [cx, cy];
fill(currColor);
// calculate distance from centroid to find new color, mod 255 to prevent value from going over 255
const centerDist = sqrt(c[0]*c[0] + c[1]*c[1]);
currColor[0] = (currColor[0] + centerDist * 20) % 255;
currColor[1] = (currColor[1] + centerDist * 10) % 255;
currColor[2] = (currColor[2] + centerDist * 30) % 255;
// draw triangle with color
triangle(
t[0][0] * SCALE,
t[0][1] * SCALE, t[1][0] * SCALE,
t[1][1] * SCALE, t[2][0] * SCALE,
t[2][1] * SCALE);
});
}
function draw() {
translate(width/2, height/8);
drawTriangles();
}The shape looks like a grouping of triangles with a series of circular regions at the corners and center where the triangles stretch out.
If you noticed, this sketch is much slower than the others. This is because we need to draw each triangle, and we have a large number of triangles. Each recursive call generates three triangles, and we recurse on each triangle. This generates 3*3*3*3… = 3 to the power of N triangles, which is exponential. This gets large fast and requires more computation each frame which slows it down.
Conclusion
Recursion is a powerful tool for generating complex shapes and geometry. We can use recursion to subdivide a shape and create self-similar shapes at different scales. It does this by calling the same function on a different version and scale of the shape. Recursion can generate shapes that iterative solutions cannot easily do, such as the finite subdivision rule and self-similar shapes.
Shapes such as those created by finite subdivision rules can be used to tile a plane. This is useful in computational geometry and other geometric fields. They can also be used in computer graphics to subdivide a surface on a mesh or polygon. In architecture, many historic sites use similar rules to produce beautiful tilings.
Others, like self-similar shapes, can be used in architecture and graphic design to generate similar designs at different scales. Scaling a shape at different levels can allow less work to be done, and there doesn’t need to be a new shape drawn for each scale if it can be done recursively.
Recursion, in this sense, minimizes the amount of work that needs to be done. Instead it is offset to to the recursive call so that the recursive call does most of the work. This is how recursion has so much power when computing anything.
I hope you enoyed this article and found the code examples useful. Next time I might delve into deeper topics.
