Simple recursion — A beginner’s tutorial.

Published by cecil on

You’re browser does not support HTML5 canvas elements.

var iterations = 10; //Default. Otherwise set by slider

var xOrigin = 300;  //The horizontal center of the 600×400 <canvas>

var yOrigin = 400;  //The bottom of the 600×400 <canvas>

var angle = Math.PI / 2;  //90 degrees in radians

var ang_change = Math.PI /6;  //30 degrees in radians

var trunkLength = yOrigin/2.5;

var canvas = document.getElementById(“myCanvas”);

var ctx = canvas.getContext(“2d”);

drawTree(xOrigin, yOrigin, trunkLength, iterations, angle)

function drawTree(x1, y1, length, iter, theta) {

if(iter <= 0){return;} //The base case

else {

var xNew = (x1 + (length*.5 * (Math.cos(theta))));  //Each branch is half as long as its parent

var yNew = (y1 – (length*.5 * (Math.sin(theta))));  //Sorry no room for a geometry lesson here

ctx.strokeStyle = ‘#ccc’;  //Sets the line color

ctx.beginPath();

ctx.moveTo(x1, y1);

ctx.lineTo(xNew, yNew);

ctx.stroke();  //Draws the line from the old coordinates to the new

console.log(iter);

drawTree(xNew, yNew, length * .8, iter-1, theta – ang_change);  //Recursive call to draw right child branch

console.log(“———” + iter);

drawTree(xNew, yNew, length * .8, iter-1, theta + ang_change);  //Recursive call to draw left child branch

console.log(“+++++++++” + iter);

}

}

var iterations = 10; //Default. Otherwise set by slider

var xOrigin = 300;  //The horizontal center of the 600×400 <canvas>

var yOrigin = 400;  //The bottom of the 600×400 <canvas>

var angle = Math.PI / 2;  //90 degrees in radians

var ang_change = Math.PI /6;  //30 degrees in radians

var trunkLength = yOrigin/2.5;

var r = 0;

var g = 0;

var b = 0;

var canvas = document.getElementById(“myCanvas”);

var ctx = canvas.getContext(“2d”);

drawTree(xOrigin, yOrigin, trunkLength, iterations, angle)

function drawTree(x1, y1, length, iter, theta) {

if(iter <= 0){return;} //The base case

else {

var xNew = (x1 + (length*.5 * (Math.cos(theta))));  //Each branch is half as long as its parent

var yNew = (y1 – (length*.5 * (Math.sin(theta))));  //Sorry no room for a geometry lesson here

var colorFade = “rgb(“+r+”,”+g+”,”+b+”)”;

ctx.strokeStyle = colorFade; //Sets the line color

if(r<255 && g<255 && b<255){r++;} //Iterates through colors

else if (r>=255 && g<255 && b<255) {g++;}

else if (r>=255 && g>=255 && b<255) {b++;}

else if (r>0 && g>=255 && b>=255) {r–;}

else if (r==0 && g>0 && b>=255) {g–;}

else if (r==0 && g==0 && b>=0) {b=0;}

ctx.beginPath();

ctx.moveTo(x1, y1);

ctx.lineTo(xNew, yNew);

ctx.stroke();  //Draws the line from the old coordinates to the new

console.log(iter);

drawTree(xNew, yNew, length * .8, iter-1, theta – ang_change);  //Recursive call to draw right child branch

console.log(“———” + iter);

drawTree(xNew, yNew, length * .8, iter-1, theta + ang_change);  //Recursive call to draw left child branch

console.log(“+++++++++” + iter);

}

}

var iterations = 10; //Default. Otherwise set by slider

var xOrigin = 300;  //The horizontal center of the 600×400 <canvas>

var yOrigin = 400;  //The bottom of the 600×400 <canvas>

var angle = Math.PI / 2;  //90 degrees in radians

var ang_change = Math.PI /6;  //30 degrees in radians

var trunkLength = yOrigin/2.5;

var green = 50;

var canvas = document.getElementById(“myCanvas”);

var ctx = canvas.getContext(“2d”);

drawTree(xOrigin, yOrigin, length, iterations, angle, green, false);

function drawTree(x1, y1, length, iter, theta, greenValue, flowers) {

if(iter <= 0){return;} //The base case

else {

var xNew = (x1 + (length*.5 * (Math.cos(theta))));  //Each branch is half as long as its parent

var yNew = (y1 – (length*.5 * (Math.sin(theta))));  //Sorry no room for a geometry lesson here

if(greenValue >= 250){ //Ensures the green value is never > max possible value (255)

greenValue = 255;

} else { greenValue += 20; }

ctx.lineWidth = 1; //Sets the line width back to default after flowers are drawn

if (iter >= iterations – 1) {

ctx.strokeStyle = ‘rgb(165, 42, 42)’; //First 2 iterations are brown

} else if(iter <=1 && flowers){ //If last iteration and flowers are selcted

ctx.strokeStyle = ‘rgb(255, 0, 0)’;

ctx.lineWidth = 3;

ctx.lineCap = ’round’;

} else {

ctx.strokeStyle = ‘rgb(0,’ + greenValue + ‘, 0)’; //Sets the line color

}

ctx.beginPath();

ctx.moveTo(x1, y1);

ctx.lineTo(xNew, yNew);

ctx.stroke();  //Draws the line from the old coordinates to the new

console.log(iter);

drawTree(xNew, yNew, length * .8, iter-1, theta – ang_change, greenValue, flowers);

 //Recursive call to draw right child branch

console.log(“———” + iter);

drawTree(xNew, yNew, length * .8, iter-1, theta + ang_change, greenValue, flowers);

 //Recursive call to draw left child branch

console.log(“+++++++++” + iter);

}

}






It may take a few seconds for iterations > 12 to compute

Higher iterations(n) take longer to compute because the function’s run time is O(2^n) aka exponential aka terrible. More precisely though the function runs (2^n)-1 times.

My intent of creating this post was to help make recursion more intuitive for someone just getting into the subject. The “Normal” version above is included to give you the foundational code for the Pythagorean tree. The “Color Fade” and the slider are designed to help you visualize the code running step by recursive step. The “Green Fade” is, well, just for fun really.

You can also open your web developer/inspector to see the output to the console which will also hopefully aid in your visualization of the process.

The code on the left changes based on your selection. To see the complete JavaScript file running on this page here