By paddloPayday loans

Home > Recursion > Recursion: An ActionScript 3.0 Problem or Problem Solver?

Recursion: An ActionScript 3.0 Problem or Problem Solver?

recursion imageWhy Recursion? (Again)

In previous posts we’ve considered recursion, and while not rejecting recursion out of hand, it’s been roughed up a bit, especially by smart reader comments. (You can see posts on recursion here.) For those of you who may be new to the recursive concept, it refers to a method that calls itself.

In general, ActionScript 3.0 programmers tend to avoid recursion because recursive functions fill up the stack faster than a loop doing essentially the same thing, and loops are generally faster than recursive functions. Now that we really need to pay attention to speed for mobile development, should we waste time thinking about recursion when we need to be thinking about speed and multicore operations? I think we need to understand recursion, and use it when needed. More importantly, it is a useful tool for thinking about programming.

Basic ActionScript 3.0 Recursive Functions: Direct and Indirect

As a simple refresher, the following illustrates two examples of recursion in programming. A direct recursive function is one where the function calls itself and indirect recursion occurs where a function calls another function and then calls the calling function.

?View Code ACTIONSCRIPT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package 
{
	import flash.display.Sprite;
	public class Recursion extends Sprite
	{
		private static var cur:String;
		private static var counter:uint = 0;
 
		public function Recursion()
		{
			direct();
			indirect();
		}
 
		//Direct recursion occurs when a method calls itself
 
		private static function direct():void
		{
			if (counter<2)
			{
				cur = "Direct recursion";
				trace(cur+counter);
				counter++;
				//Self-calling method
				direct();
			}
		}
 
		//Indirect recursion occurs when a method calls a method 
		//that calls the calling method
 
		private final function indirect():void
		{
			if (counter < 4)
			{
				cur = "Indirect recursion";
				trace(cur+counter);
				counter++;
				//Calls method that calls this method
				indirectly();
			}
		}
 
		private final function indirectly():void
		{
			indirect();
		}
	}
}

The conditional statements inside the recursive functions keep the functions from a stack overflow error. It is identical to avoiding an infinite loop by making sure that a loop termination condition is placed in the loop statement.

Gödel, Escher, Bach: An Eternal Golden Braid (A metaphorical fugue on minds and machines in the spirit of Lewis Carroll)

Wanting to dust the cobwebs out of my head and get away from linear thinking, I inquired for a good starting point for pure mathematics. I was guided to Gödel, Escher, Bach (GEB) by Douglas R. Hofstadter. Published in 1979, it won the nonfiction Pulitzer Prize in 1980 and has been a perennial favorite of programmers, mathematicians, artists, musicians and others who want to give their minds a workout ever since. (See the WikiPedia entry for a quick overview. Also, MIT offers GES: A Mental Space Odyssey as part of their Open Courseware program.) Of particular interest for this post is Chapter V: Recursive Structures and Processes (Canon by Intervallic Augmentation). For Hofstadter, recursion is a general concept and can include such things as movies within movies, Russian stacking dolls and paintings inside paintings. (The image at the beginning of this post is borrowed from Escher’s famous illustration of two hands drawing one another—a recursive illustration.)

One type of recursion occurs in graphics where the pixels that define a shape (context) are defined by the context. For example, consider Figure 1. The dots that make up the circle shape are also positioned relative to the circle they define.

recursive

Figure 1: Dots' positions defined by the circle they define.

The gray arrow points to a dot in the upper left of the circle. The location “upper left” is relative to the circle that the dots define. The recursive nature of the position is that the defining building block (dot) is relative to the structure it defines (circle).

The dot (or pixel) is part of the images we seek to place on the stage, and their placement makes up the image that defines their position. You may be thinking,

So what?

How can I use this knowledge to become a better programmer or make my programs better? You can do it in the same way that Gamma and his associates looked a programming in a different way and came up with Design Patterns. Instead of asking,

What will make my program run faster and how can I optimize its performance?

They asked,

What kind of program structures do we need when programs change so that the other parts of the program will be unaffected by the change?

Perhaps instead of asking “How do I make a circle by lighting up pixels?”, we may ask, “How do circles position pixels?” They’re the same question, but they generate different ways of thinking about creating graphics in ActionScript 3.0. Of course, AS3 has built-in Graphics methods for creating circles; so you may not think about creating circles. (See Circle-Drawing Algorithms for an interesting discussion of circle creation.) However, in terms of problem-solving, you will find recursion again and again. Recursion is in the world, and linear thinking is not the only way to think about recursion. In some respects linear thinking distorts reality because it distorts recursion by unwinding it to fit into a linear plan.

Design Patterns as Cheat Sheets for Critical Thinking

Like recursion, a lot of the principles in the GoF book are nonlinear. For example the principle, Program to the interface and not the implementation, is a good example of nonlinear thinking. The fact that the Gang of Four took the time to work out the set of patterns they did for the different kinds of programming structures is very valuable because that means I don’t have to do it for myself. For example, if I have a bunch of algorithms that I know are going to change and interact with the rest of the program, I don’t have to figure out a flexible way to incorporate them into my program. I can snatch up a Strategy pattern and it has the structure laid out for me. In the same way, the concept of recursion is a structure that can be used to help solve a problem. I may end up using a loop, but I’m more likely to first think, “Is this a recursive structure?” If so, then I can add a recursive method (as I might in a Chain of Responsibility structure) and then eventually solve the problem using a switch statement inside a loop. In that respect, recursive methods are cheat sheets as well. We don’t have to reinvent new structures or rely only on linear ones when we sit down to program.

Share
Categories: Recursion
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>