``````<iframe  id='recursion'></iframe>

<script>
const recursion_frame = document.getElementById ('recursion')
recursion_frame.width = recursion_frame.parentNode.scrollWidth
recursion_frame.height = recursion_frame.width
const i = !location.search ? 1 :
Number (location.search.split ("?").pop ()) + 1
if (i < 12) {
const path = `/rmit/ccs/2022/09/03/recursion.html?\${ i }`
recursion_frame.src = `http://thomas.capogre.co` + path
}
</script>
``````

*inspired by the Creative Coding Enhancement students at Preston High School 🚀

**also inspired by this blog post by Bryan Braun 🤓

## To understand recursion

… you must first understand recursion.

At its heart, recursion is self-reference. Recursive functions are functions that call themselves. You could call it a fancy way of iterating, but I believe the history of recursive functions may in fact pre-date for-loops, so maybe a better description might be the OG way of iterating. However, recursion can do branching self-similarity, something which is very clunky, if not impossible, to engineer merely with for-loops. We will explore the idea of branching self-similarity in the examples that follow.

This post will explore some of the ideas from The Coding Train: Algorithmic Botany, which we will endeavour to recreate without p5, in plain javascript (ie. with Canvas API).

edit: The Coding Train have since made video employing recursion to code a fractal tree on an Apple II+. Have a look here.

## Vectors: a sensible provision

First let’s define a `Vector` class to help manage some of the trigonometry we will need to use:

``````const TAU = Math.PI * 2

class Vector {
constructor (x, y) {
this.x = x
this.y = y
}

this.x += v.x
this.y += v.y
}

subtract (v) {
this.x -= v.x
this.y -= v.y
}

mult (m) {
this.x *= m
this.y *= m
}

mag () { // using a^2 + b^2 = c^2
return ((this.x ** 2) + (this.y ** 2)) ** 0.5
}

setMag (m) {
this.mult (m / this.mag ())
}

rotate (a) {
// from "Formula for rotating a vector in 2D" by Matthew Brett
// https://matthew-brett.github.io/teaching/rotation_2d.html

const new_x = (this.x * Math.cos (a)) - (this.y * Math.sin (a))
const new_y = (this.x * Math.sin (a)) + (this.y * Math.cos (a))

this.x = new_x
this.y = new_y
}

clone () {
return new Vector (this.x, this.y)
}
}

function vector_from_angle (angle, magnitude) {
const x = magnitude * Math.cos (angle)
const y = magnitude * Math.sin (angle)
return new Vector (x, y)
}
``````

I’ve added a `.rotate ()` method, inspired by this blog post by Matthew Brett.

Let’s whip up a quick test sketch:

``````<canvas id='rotation_test'></canvas>

<script type='module'>
// using a 'module' type here keeps
// the scope seperate from the global scope
// this is helpful as I will want to reuse
// 'cnv' and 'ctx' variable names later

// get and format canvas element
const cnv = document.getElementById ('rotation_test')
cnv.width = cnv.parentNode.scrollWidth
cnv.height = cnv.width * 9 / 16

// get cavnas context
const ctx = cnv.getContext ('2d')

// vector to the centre of the canvas
const mid = new Vector (cnv.width / 2, cnv.height / 2)

// vector going straight up, with a magnitude
// equal to half the height of the canvas
const hand = new Vector (0, mid.y * -1)

// declare mutable variable to count the seconds
let seconds = 0

// function describing each tick of the clock
function tick () {

// cloning the hand vector so transformations
// won't affect the original
const abs_hand = hand.clone ()

// to get the absolute position

// drawing a line Canvas API style
ctx.beginPath ()
ctx.moveTo (mid.x, mid.y)
ctx.lineTo (abs_hand.x, abs_hand.y)
ctx.stroke ()

// rotating the original hand vector
hand.rotate (TAU / 60)

// iterating the seconds counter
seconds++

// if less than 60 seconds
// call tick again, after 1000 milliseconds
if (seconds < 60 ) setTimeout (tick, 1000)
}

// calling tick once to set off the recursive sequence
tick ()
``````

Looks like the new `.rotate ()` method is working as intended:

A quick note – because the function `tick` above uses `setTimeout` to call itself, we are using recursion already!

## Fractal Tree via Recursive Function

from this video.

``````<canvas id='fractal_tree_0'></canvas>

<script type='module'>

// get and format canvas
const cnv = document.getElementById ('fractal_tree_0')
cnv.width = cnv.parentNode.scrollWidth
cnv.height = cnv.width * 9 / 16

// get canvas context
const ctx = cnv.getContext ('2d')

// this is the recursive function that will draw the tree
// it accepts three arguments:
// base: vector describing the starting position
// stem: vector describing the new line
// generation: integer limiting the number of recursions
function tree (base, stem, generation) {

// we want to tranform it, so we make a copy
const end = base.clone ()

// add the stem to the start position

// draw the line from the start point
// to the end point
ctx.beginPath ()
ctx.moveTo (base.x, base.y)
ctx.lineTo (end.x, end.y)
ctx.stroke ()

// if generations is still positive
if (generation > 0) {

// clone the stem
const L_stem = stem.clone ()

// rotate it anti-clockwise
L_stem.rotate (-TAU / 7)

// reduce the length
L_stem.mult (0.6)

// clone the stem again
const R_stem = stem.clone ()

// rotate this one clockwise
R_stem.rotate (TAU / 7)

// reduce its length
R_stem.mult (0.6)

// decrease generation by 1
const next_gen = generation - 1

// recursively call tree twice,
// with end as the new base
// L_stem & R_stem as the new stems
// and next_gen as the new generation
tree (end, L_stem, next_gen)
tree (end, R_stem, next_gen)
}
}

// new vector defining the starting point of our tree
const seed = new Vector (cnv.width / 2, cnv.height)

// new vector defining the first stem
// ie. 150 pixels straight up
const shoot = new Vector (0, -150)

// pass seed in as the base argument
// shoot as the stem argument
// and 7, denoting that we want 7 recursions
tree (seed, shoot, 7)
</script>
``````

We can randomise things somewhat to get some interesting results. Click for a new tree:

``````<canvas id='fractal_tree_1'></canvas>

<script type='module'>
const cnv = document.getElementById ('fractal_tree_1')
cnv.width = cnv.parentNode.scrollWidth
cnv.height = cnv.width * 9 / 16

const ctx = cnv.getContext ('2d')

// define a function to return a random value
// between a minimum and maximum
function rand_between (min, max) {
const dif = max - min
const off = Math.random () * dif
return  min + off
}

// this function has been modified to recieve
// an options object housing angle and mult data
function tree (base, stem, generation, options) {
const end = base.clone ()

ctx.beginPath ()
ctx.moveTo (base.x, base.y)
ctx.lineTo (end.x, end.y)
ctx.stroke ()

if (generation > 0) {
const L_stem = stem.clone ()

// use the data in the options object
// for the left angle
L_stem.rotate (options.angle.l)

// for the left multiplier
L_stem.mult (options.mult.l)

const R_stem = stem.clone ()

// for the right angle
R_stem.rotate (options.angle.r)

// and for the right multiplier
R_stem.mult (options.mult.r)

const next_gen = generation - 1

// pass the options object
// on to the next generation
tree (end, L_stem, next_gen, options)
tree (end, R_stem, next_gen, options)
}
}

const seed = new Vector (cnv.width / 2, cnv.height)
const shoot = new Vector (0, -150)

// function for a new tree
function new_tree () {

// clear the canvas
ctx.fillStyle = `white`
ctx.fillRect (0, 0, cnv.width, cnv.height)

// create an options object
// using object literal notation
const options = {
mult : {
l : rand_between (0.5, 0.8),
r : rand_between (0.5, 0.8),
},

angle : {
l : rand_between (TAU / 12, TAU / 4) * -1,
r : rand_between (TAU / 12, TAU / 4),
}
}

// grow a tree using the options generated
tree (seed, shoot, 8, options)
}

// assign the new_tree function to the
// .onclick property of the canvas
cnv.onclick = new_tree

// make a tree
new_tree ()
</script>
``````

## Objects: a brief detour

Note that I am using object literal notation to package my options together and pass them to the `tree ()` function. This is quite a common occurance in javascript, and can be a handy way of organising discrete bits of data that you want to pass around together.

As an example, this declaration:

``````const thelonious = { species: 'cat' }
``````

… stores in the the variable `thelonious` an object with the property, `species`. Executing `console.log (thelonious.species)` would print `'cat'` to the console. Inside the curly braces, properties (or key-value pairs) are indicated with a colon `:` and seperated by a comma `,`. For example:

``````const thelonious = { species: 'cat', preoccupation: 'naps' }
``````

In this case, `thelonious.species` returns `'cat'`, and `thelonious.preoccupation` returns `naps`. We could format it like this:

``````const thelonious = {
species: 'cat',
preoccupation: 'naps'
}
``````

We could further specify Thelonious’ preoccupation into primary and secondary by doing something like this:

``````const thelonious = {
species: 'cat',
preoccupation: {
primary: 'naps',
secondary: 'snacks'
}
}
``````

Here we are giving the `preoccupation` property an object with `primary` and `secondary` properties. `thelonious.preoccupation.secondary`, for example, returns the string `'snacks'`.

You could format it like this if you want the colons to line up:

``````const thelonious = {
species       : 'cat',
preoccupation : {
primary   : 'naps',
secondary : 'snacks'
}
}
``````

The options declaration, in the `new_tree ()` function in the above example, uses this type of nested object structure:

``````const options = {
mult : {
l : rand_between (0.5, 0.8),
r : rand_between (0.5, 0.8),
},

angle : {
l : rand_between (TAU / 12, TAU / 4) * -1,
r : rand_between (TAU / 12, TAU / 4),
}
}
``````

… storing randomised values in the `l` and `r` properties of the objects assigned to the `mult` and `angle` properties of the `options` object. When the options object is passed to the `tree ()` function (and subsequent recursive calls of the `tree ()` function), those generated values are retrievable within that scope, and are used for the vector transformations all the way up the recursion tree, as we can see in this code excerpt:

``````const L_stem = stem.clone ()

// use the value stored on the .l property of
// the object stored on the .angle property of
// the options object:
L_stem.rotate (options.angle.l)

// use the value stored on the .l property of
// the object stored on the .mult property of
// the options object:
L_stem.mult (options.mult.l)

const R_stem = stem.clone ()

// use the value stored on the .r property of
// the object stored on the .angle property of
// the options object:
R_stem.rotate (options.angle.r)

// use the value stored on the .r property of
// the object stored on the .mult property of
// the options object:
R_stem.mult (options.mult.r)

const next_gen = generation - 1

tree (end, L_stem, next_gen, options)
tree (end, R_stem, next_gen, options)
``````

## Fractal Tree via Recursive Object

We can do a similar thing, but with a class constructor instead of a function:

``````// class definition
class Tree {

// constructor receiving all the arguments
// the recursive function did
// plus the canvas context
constructor (base, stem, generation, options, ctx) {

// storing all the arguments passed in
// as properties of the new object
this.base       = base
this.stem       = stem
this.generation = generation
this.options    = options
this.ctx        = ctx

// create an empty array for the branches
this.branches   = []

// unless this is the last generation
if (generation > 0) this.add_branches ()

// arbitrary width, dialed in via trial + error
this.sway_width = 0.03

// random ish sway rate
// as this.generation decreases
// towards the top of the tree
// the sway rate gets faster
this.sway_rate  = Math.random () * 2 / this.generation
}

// a method to add more branches

// this is to find the absolute position
// of the end of the branch
const end = this.base.clone ()

// add the stem (relative position)
// to the absolute position of the base

// clone the stem for the L branch
const L_stem = this.stem.clone ()

// transform it according to the values
// stored in the options object
L_stem.rotate (this.options.angle.l)
L_stem.mult (this.options.mult.l)

// do the same for the R branch
const R_stem = this.stem.clone ()
R_stem.rotate (this.options.angle.r)
R_stem.mult (this.options.mult.r)

// decrease the generation number
const next_gen = this.generation - 1

// create two new Tree objects
const l = new Tree (end, L_stem, next_gen, this.options, this.ctx)
const r = new Tree (end, R_stem, next_gen, this.options, this.ctx)

// push both into the .branches array
this.branches.push (l)
this.branches.push (r)
}

// the draw funcion accepts a now argument
// which is the time in seconds
draw (now) {

// calculates the phase between 0 - 1
const sway_phase = (now * this.sway_rate) % 1

// turns the phase into a sinusoid
// with an amplitude = this.sway_width
const sway_angle = Math.sin (sway_phase * TAU) * this.sway_width

// we will make a new stem to rotate
const sway_stem = this.stem.clone ()

// rotate it with the sway angle
sway_stem.rotate (sway_angle)

// new absolute end point
const end = this.base.clone ()

// add the swaying stem to get
// the new absolute position
// of the end of the stem

// draw the line
this.ctx.beginPath ()
this.ctx.moveTo (this.base.x, this.base.y)
this.ctx.lineTo (end.x, end.y)
this.ctx.stroke ()

// for each of the branches
this.branches.forEach (b => {

// assign the new absolute end point
// as the branches base keeping the
// branches attached to each other
b.base = end.clone ()

// call the branch's .draw method
b.draw (now)
})
}
}
``````
``````<canvas id='recursive_object_tree'></canvas>

<script type='module'>

// get and format the canvas element
const cnv = document.getElementById ('recursive_object_tree')
cnv.width = cnv.parentNode.scrollWidth
cnv.height = cnv.width * 9 / 16

// get canvas context
const ctx = cnv.getContext ('2d')

// these option values give a nice tree, I think
const options = {
mult : {
l : 0.6,
r : 0.7,
},

angle : {
l : -TAU / 4,
r :  TAU / 7,
}
}

const seed = new Vector (cnv.width / 2, cnv.height)
const shoot = new Vector (0, -150)

// this time constructing an object with the class
// passing it the same arguments, and also the
// canvas context, then storing it in a variable
const tree = new Tree (seed, shoot, 8, options, ctx)

// function to draw the frames
// accepts the argument 'now'
// which requestAnimationFrame will pass
// the current time to, in milliseconds
function draw_frame (now) {

// clear the canvas
ctx.fillStyle = `white`
ctx.fillRect (0, 0, cnv.width, cnv.height)

// convert time to seconds
// and pass to .draw method of tree
tree.draw (now / 1000)

// wait for the next frame
// then call draw_frame again
requestAnimationFrame (draw_frame)
}

// initiate the animation
requestAnimationFrame (draw_frame)
</script>
``````

There are many good resources on recursion: