Bookmark this on Hatena Bookmark
Hatena Bookmark - Super Easy Programming #5: More Fun with Functions
Share on Facebook
Post to Google Buzz
Bookmark this on Yahoo Bookmark
Bookmark this on Livedoor Clip
Share on FriendFeed

Last time I promised you an introduction to game programming, but it appears that the series “shi3z Game Programming” will be covering that. Instead, let me go into a little more depth about the fun of programming!

This time, let’s talk about something called “recursions.”

What on earth is a “recursion?”

Recursions will enable you to create stuff like this!

Let’s give it a go.

(continued after the link)

A few posts back, we talked about something called functions.

What happens if we call up functions with functions?

How to explain?

So far we’ve used the principal function onLoad, and then defined and called up functions we defined ourselves, like circle or random.

Naturally, one can easily call up functions from within functions.

So, what happens when we call up functions from functions?

You get a mess. The code below is a sample, but DO NOT try it out. You might very well bust your browser.

function onLoad(){
onLoad(); // What happens here?
}

A clever browser like Safari gives us this warning. So, what exactly does it mean?

maximum call stack size exceeded

As it turns out, herein lies the secret of calling up functions. You may call up functions freely, but not without limit.

In other words, there is a limit to number of times you can call up a function. This is called “call stack size.”

If you call up an unconditional onLoad function within an onLoad function, this calls up new onLoad functions without limit.

As a result, no matter how large you set the “maximum call stack size,” you are virtually guaranteed to exceed it.

The call stack size is set at a perfectly reasonable size, but if you call up functions infinitely you’re bound to reach this error.

Why on earth does such a dangerous function…one with the power to call up itself…exist?

As it turns out, if you use it properly, it can be extremely useful. It’s a technique called “recursions.”

Take a look at the following code.

function onLoad(){
var proc = function(t){
if(t<1) // Ends recursion when t falls below 1.
return;
for(var i=0;i<360;i++){ // Draws a circle.
move(t);
turn(1);
}
proc(t*0.8); // Multiplies t by 0.8 and draws a circle again.
};
penDown();
proc(3);
logo.penUp();
}

When you execute, it turns out like this:

This time we executed without any difficulties in the browser.

What’s going on here? As you can see, proc is being called up many multiple times. Alert can help you easily understand this program.

Rewrite the program as you see below.

function onLoad(){
var proc = function(t){
alert(“t=”+t);
if(t<1) // Ends recursion when t falls below 1.
return;
for(var i=0;i<360;i++){ // Draws a circle.
move(t);
turn(1);
}
proc(t*0.8); // Multiplies t by 0.8 and draws a circle again.
};
penDown();
proc(3); // Assigns 3 to the first level of t.
logo.penUp();
}

Each time “proc” is called up, the “t” level will be displayed in alert. At first, the “t” level is 3.

The next is “t=2.4000000000000004,” or in other words about 2.4, then 1.92, 1.536, 1.2288, and when it hits 0.98304 next it is less than 1 and so recursions end.

Take a look at the image on the right. Each time the recursion repeats the radius of the circle gets progressively smaller.

In this way, recursions allow a limit to be established while calling up a function itself.

Does this seem difficult? Recursions require quite a lot of experience before you can get used to them. If do learn how to use recursions, however, you can truly claim to be a self-reliant programmer.

Let’s end with a graphic for drawing a tree using recursions.

function onLoad(){
a=20;
b=0.8;
var proc = function(t){
if(t<10){ //  Ends recursion when the level of t falls below 10.
move(t*b); // Continue.
move(-t*b); // Return.
return;
}
turn(-a*b);
move(t*b);
proc(t*b); // Calls forth function itself (recursion callup).
move(-t*b);
turn(a*b);
turn(a);
move(t*b);
proc(t*b); // Calls forth function itself (recursion callup).
move(-t*b);
turn(-a);
};
penUp();
turn(180);
move(-100);
penDown();
proc(80);
logo.penUp();
}

You getting an idea of what will happen? In order to get the hang of this program, it’s a good idea to change up the numbers and move around move and turn.

There’s nothing particularly shocking going on here. Just the help of recursions.

Watch out for endless recursions, and have fun!