Recursion in Flash
Recursion is a programming technique that is used in many important applications such as “sorting”, “parsing”, and “searching” among many others.
Many programmers shy away from using this techniques because the logic behind it can be quite abstract. However, the basic idea of recursion is a function that calls itself in a finite number of times. Finiteness is a very important part to consider when dealing with recursion, since it is very easy to get an infinite loop when doing recursion. Recursive calls utilize the stack, as such the first call to the recursive function will eventually finish last (LIFO).
In this post, I am going to show one of the most widely used recursion example, i.e. drawing a tree branch. However, if you are interested to see how recursion can be used for “sorting” (QuickSort algorithm in this case - one of the faster sorting algorithm), feel free to download it here.
Here is a preview of the final product:
To begin, let’s take a look at the complete code first:
var pi:Number = Math.PI;
function drawBranch(start_x:Number, start_y:Number, color:Number, length:Number, angle:Number, thickness:Number, level:Number):Void {
if (level > 0) {
this.lineStyle(thickness, color, 100);
this.moveTo(start_x, start_y);
var end_x:Number = start_x-length*Math.cos(angle);
var end_y:Number = start_y-length*Math.sin(angle);
this.lineTo(end_x, end_y);
--level;
drawBranch(end_x, end_y, color << 1, length/1.4, angle+pi/4, thickness/2, level);
drawBranch(end_x, end_y, color << 1, length/1.4, angle-pi/4, thickness/2, level);
}
}
drawBranch(100, 120, 0x993300, 20, pi/2, 8, 10);
Let’s look at the following line
var pi:Number = Math.PI;
The purpose of this is just to store value of Math.PI. The reason I put it here and not inside of the function is for optimization by avoiding multiple Math.PI calls
The next line of code is
function drawBranch(start_x:Number, start_y:Number, color:Number, length:Number, angle:Number, thickness:Number, level:Number):Void {
It is just the function declaration with a whole bunch of parameters that is dynamic according to the recursion level.
The next line of code is
if (level > 0) {
This is a vital part of the code. This is what defines the finiteness of your recursive function. Without this, your recursive function will go in an infinite loop.
The next line of codes is
this.lineStyle(thickness, color, 100);
this.moveTo(start_x, start_y);
var end_x:Number = start_x-length*Math.cos(angle);
var end_y:Number = start_y-length*Math.sin(angle);
this.lineTo(end_x, end_y);
This is what draws the tree branch. It utilizes the Flash drawing API. There are many good tutorials out there if you are not familiar with them. But basically this.lineStyle(thickness:Number, color:Number, alpha:Number) is what defines the style of your line stroke. this.moveTo(x:Number, y:Number) position the starting point of your line. this.lineTo(x:Number, y:Number) position the ending point of your line. So your line will drawn from those 2 points that you define here.
The next line of code is
--level;
This is another vital part of the code. This code is what makes the finiteness rule (in this case, if (level > 0)) of this code possible.
The next line of codes is
drawBranch(end_x, end_y, color << 1, length/1.4, angle+pi/4, thickness/2, level);
drawBranch(end_x, end_y, color << 1, length/1.4, angle-pi/4, thickness/2, level);
This is the recursive call. Notice how it is calling the function itself. Also notice the difference between the 2 lines. One has angle+pi/4 and the other has angle-pi/4. The only reason for calling it twice is because your tree will be 1 sided otherwise.