This short tutorial explains how recursion works and why it is a useful technique in certain situations.
The benefit of recursion is that different procedures can be nested in any combination.
Or to put it another way:
"Recursive functions are to functions as functions are to subroutines."
* Subroutines handle one instance of a procedure with one set of parameters.
* Functions handle one instance of a procedure with multiple sets of parameters.
* Recursive functions handle multiple instances of a procedure with multiple sets of parameters.
Let's say we wanted to produce an output that looks like this:
Hello, Please join me in the next indentation level.
Ah, there you are!
Oh it's far too loud in here!
Let's leave.
Okay now we might have a bit of peace in here:
Yes that's better.
So how would we code something like that? Well let's see it without recursion.
tab = 20
text x,y, "Hello, Please join me in the next indentation level."
inc y,16
text x+tab,y, "Ah, there you are!"
inc y,16
text x+tab,y, "Oh it's far too loud in here!"
inc y,16
text x+tab,y, "Let's leave."
inc y,16
text x,y, "Okay now we might have a bit of peace in here:"
inc y,16
text x+tab,y, "Yes that's better."
Getting a sense of deja vu when scanning over a block of code is a sure sign that things can be tidied away into conditional loops and/or functions, and these lines certainly look alike! If you're confident with arrays you'll have spotted that we could dump those strings into one and reference them by the index number. That's a good start, but how on earth are we going to deal with that pesky "+tab"? It doesn't appear at regular intervals, and ideally the placement of each tab should be variable so that we can use this code to display more than one message. (It would be a pretty useless program if it couldn't.) What we need is some way of telling the program when to add a tab-space and when to remove one. Maybe we could do this:
dim ln$(5)
ln$(0) = "Hello, Please join me in the next indentation level."
ln$(1) = "Ah, there you are!"
ln$(2) = "Oh it's far too loud in here!"
ln$(3) = "Let's leave."
ln$(4) = "Okay now we might have a bit of peace in here:"
ln$(5) = "Yes that's better."
tab = 20
for n = 0 to 5
select n
case 1, 5
inc x,tab
endcase
case 4
dec x,tab
endcase
endselect
text x,n*16, ln$(n)
next n
Better? Well the problem is that if we want the program to be flexible we'd need a different case statement for each line and use variables for each too. Alternatively we could store the indentation level of each line in another array and reference it like the strings:
dim x(5)
x(0) = 0 : x(1) = 20 : x(2) = 20 : x(3) = 20 : x(4) = 0 : x(5) = 20
tab = 20
for n = 0 to 5
text x(n),n*16, ln$(n)
next n
Yay! ... What, still not good enough? Well this is much better than what we started with but looking at all those x's is already confusing, and we only have six lines! There's just no good way to get the amount of flexibility we want without using recursion.
Now we're onto the good part! What makes recursion useful is the fact that functions use local variables that have a specific value to that function call. Check out this example:
r = add(1,1,3)
print "Result: "; r
wait key
end
function add(a,b,times)
print a
if times >0 then add(a+b,b,times-1)
endfunction a
The output counts up to 4 but the function only returns 1. This demonstrates that the first call hasn't forgotten its value for 'a', but what happened to the subsequent values? Let's make a diagram to help visualize what happens when we run the code:
PSEUDO CODE
{} Holds the code activated by the function call.
r = add(a = 1, b = 1, times = 3)
{
if times > 0 then add(a = a+b, b = b, times = times-1)
{
// Now a = 2, b = 1, and times = 2
if times > 0 then add(a = a+b, b = b, times = times-1)
{
// Now a = 3, b = 1, and times = 1
if times > 0 then add(a = a+b, b = b, times = times-1)
{
// Now a = 4, b = 1, and times = 0
if times > 0 then add(a = a+b, b = b, times = times-1)
// times is no longer >0 so we continue to the next line, which is the end of the function.
endfunction a
}
// Now we're back we can move on to the next line.
endfunction a
}
// Now we're back we can move on to the next line.
endfunction a
}
// Now we're back we can move on to the next line.
endfunction a
}
PRINT "Result: "; r
The difference between the first call and all subsequent calls is that we're storing the return value in 'r', but when we return from the recursive calls to the function 'a' has nowhere to go and is forgotten.
Let's fix that and see what happens:
r = add(1,1,3)
print "Result: "; r
wait key
end
function add(a,b,times)
print a
if times >0 then a = add(a+b,b,times-1)
endfunction a
A tiny change, but an important lesson in recursion.
You might expect the result to be 2, since the first call (the one that actually returns a value to the main program) get's its new 'a' value from the second call, but remember that the 2nd had its 'a' changed by the 3rd call, and the 3rd by the 4th! It's only when we reach the 4th call that 'times' reaches zero, the journey ends and all the function calls collapse in on each other. 'a' is not changed again before 'endfunction a'
so the value from call 4 gets passed right back up to the main program.
Examples
Procedural Island Generator
Spirals:
set window off
set display mode 1024,768,32
sync on
sync rate 30
sync
ink -2,0
center text 512,100,"This program will demonstrate how recursion can be employed to draw spirals using the same maths required to draw circles."
center text 512,200,"CIRCLE"
drawCircle(512,384,100)
sync
wait key
cls
center text 512,200,"10 Degree Spiral"
drawSpiral(512,384,100,0,10)
sync
wait key
cls
center text 512,200,"30 Degree Spiral"
drawSpiral(512,384,100,0,30)
sync
wait key
for sect = 0 to 60
cls
center text 512,200,str$(sect)+" Degree Spiral"
drawSpiral(512,384,100,0,sect)
sync:wait 10
next sect
wait key
for sect = 60 to 0 step -1
cls
center text 512,200,str$(sect)+" Degree Spiral"
drawSpiral(512,384,100,0,sect)
sync:wait 10
next sect
wait key
end
`--- Functions ------------------------------------------------------------------------------------
function drawCircle(x,y,r)
for a = 0 to 359
dot x + sin(a)*r, y + cos(a)*r
next a
endfunction
`//
function drawSpiral(x,y,r,startA,sect)
for a =startA to startA+sect
dot x + sin(a)*r, y + cos(a)*r
next a
if r>1 then drawSpiral(x,y,r-1,a,sect)
endfunction
`//
Recursive Text Parser:
remstart
OBESIC Language Interpretor by OBese87.
OBESIC stands for: Obvious Bloody Easy Syntax for Idiotic Coders.
-----------------------------------------------------------------------------------------------
remend
open to read 1,"blarg.txt"
max = 99
dim a$(max)
lines = 0
while file end(1) =0
inc lines
read string 1,a$(lines)
endwhile
rem fileEnd is a global constant. (Array used for DBC compatability.)
dim fileEnd(0)
fileEnd(0) = lines
rem Y is a global to ensure we keep moving down the page. (Array used for DBC compatability.)
dim y(0)
y(0) = 0
readLn(0,"",0,-2)
wait key
end
function readLn(i,inTag$,x,color)
for n = i to fileEnd(0)
n$ = a$(n)
rem get command
com$ = upper$(split$(n$," ",0))
rem Drop out of the current tag when a matching close tag is found.
if mid$(com$,1)="/" and right$(com$,len(com$)-1)=inTag$ then exitfunction n
rem Execute the command tag.
select com$
case "PRINT"
ink color,0
a$ = split$(n$," ",1)
text x,y(0),a$
y(0) = y(0)+16
endcase
case "COLOR"
subcolor = val(split$(n$," ",1))
n = readLn(n+1,com$,x,subcolor)
endcase
case "TAB"
n = readLn(n+1,com$,x+20,color)
endcase
endselect
next n
endfunction n
`//
rem Returns the left- or right-most part of a string split at 'find$'.
rem 'find$' itself is omitted from the return string.
rem To split the source string at the first instance of 'find$':-
rem give 'part' a value of 0 (to return left half) or 1 (to return right half).
rem If you wish to split the string at a further instance of 'find$' simply increase
rem 'part' by 2 for every instance you wish to skip.
rem If the search fails the source string is returned.
function split$(s$,f$,part)
for x = 0 to len(s$)-len(f$)
if midleft$(s$,x,len(f$)) = f$
select part
case 0 : exitfunction left$(s$,x) : endcase
case 1 : exitfunction right$(s$,len(s$)-len(f$)-x) : endcase
case default : s$ = midleft$(s$,x+1,len(s$)) : dec part,2 : endcase
endselect
endif
next x
endfunction s$
`//
rem Returns a section of the source string starting at 'pos' and extending 'wid' characters.
function midleft$(a$,pos,wid)
a$ = right$(left$(a$,pos+wid),wid)
endfunction a$
`//
Example Text Parser File:
print Hello World!
color 16711680
print IMPORTANT THINGS IN RED!!!
tab
Print Right, now lets... oh it's still red. xD
color 65535
Print That's Better, now where was I? Oh let's start a new tab...
tab
print Right! This time we are going to get the important stuff done.
Print I would make a list but... that's not in the commands.
/tab
/color
print I see why html is moving away from using <FONT> and the like and
tab
print using style-sheets instead. All these tags are messy!
/tab
/tab
/color
print Okay so probably not as messy as this but... oh we're back to normal.
print How boring... well, see ya!
Have fun playing around with the examples and see what interesting things you can make using recursion.
Meanwhile...
