Recursion: 4 ways to get it working

[TempodiBasic]

What say about recursion:
there are many definitions but those posted by SMcNeill and others are a good explanation.


Here some other words spent about recursion:
1. in the era of DOS Recursion was in competition with Iteration for speed to do some jobs. Today it seems there is no such difference of time, but  runtime seems very related to the structure of algorythm!

Here an algorythm of filling with a color an area except the points that have the bordercolor.

Code: (Select All)

'floodfill by recursive method
'Chosen a matrix of X width and of Y height
' chosen a color of filling
' chosen a border color
' chosen a random start point
' the task is to fill with the color of filling  all the near point/cell/square
' that has no border color and is in the matrix X,Y

Screen 0 ' we are using a standard textmode 80x25
Dim As Integer BorderColor, FillColor, BackColor, Square(1 To 80, 1 To 25), XX, YY
Randomize Timer
BorderColor = 1 ' bordercolor  ranges between 1 and 7
FillColor = 3 ' fillcolor ranges between 1 and 7
BackColor = 0 ' backcolor ranges between 1 and 7

Cls
Color 15
Print " Beginning state"
InitGrid Square(), BorderColor, BackColor
_Delay 2
ShowGrid Square()
_Delay 2
Cls
Print "now it starts to fill with Fillcolor the square starting from a point of screen chosen at random"
_Delay 2
XX = Int(Rnd * 79) + 1
YY = Int(Rnd * 24) + 1
fillGrid XX, YY, Square(), FillColor, BorderColor ' this is the recursive SUB
Color 7, 0
End

Sub fillGrid (A As Integer, B As Integer, Sq( ,) As Integer, Fc As Integer, Bc As Integer)
    If SetPoint(Sq(), A, B, Fc, Bc) = -1 Then
        ShowGrid Sq()
        If (A - 1) > 0 Then fillGrid (A - 1), B, Sq(), Fc, Bc ' left
        If (A + 1) < 81 Then fillGrid (A + 1), B, Sq(), Fc, Bc ' right
        If B - 1 > 0 Then fillGrid A, (B - 1), Sq(), Fc, Bc ' up
        If B < 25 Then fillGrid A, (B + 1), Sq(), Fc, Bc 'down
    Else
        ShowGrid Sq()
        Exit Sub
    End If
End Sub

Function SetPoint (squarE( ,) As Integer, X As Integer, Y As Integer, Fill As Integer, Border As Integer)
    SetPoint = -1
    If squarE(X, Y) <> Border And squarE(X, Y) <> Fill Then squarE(X, Y) = Fill Else SetPoint = 0
End Function

Sub ShowGrid (S( ,) As Integer)
    Shared BorderColor As Integer
    For a = 1 To 80
        For b = 1 To 25
            Locate b, a
            Color 15, S(a, b)
            Print _Trim$(Str$(S(a, b)));
        Next b
    Next a
End Sub

Sub InitGrid (S( ,) As Integer, BorderColor As Integer, BackColor As Integer)
    For a = 1 To 80
        For B = 1 To 25
            S(a, B) = BackColor
        Next B
    Next a
    S(10, 4) = BorderColor
    S(10, 3) = BorderColor
    S(22, 3) = BorderColor
    S(24, 3) = BorderColor
    S(10, 13) = BorderColor
End Sub

As we run the code we see how fastly the program fills with 3 all the points except the points with bordercolor (1).
Watching more accurately we see that from ending to fill with 3 the screen and the real time of ending with the message "press any key to continue" there is an amount of time. This amount increases when we add a little _DELAY 0.02 in the SUB ShowGrid at its end.
Why does it happen?  It is showed at point 2


2. 
in the RAM the recursion is a tecnique that makes more copies of a SUB/FUNCTION into the RAM as parent child structure. In other words, each SUB is a closed box and in the recursion tecnique we create a series of boxes one into the following like the matriosca. So it uses more RAM than an Iterative Loop. Moreover when the recursive calling stops, the flow of code comes back from the last istance of SUB to the previous until the first.

In the demo above, about filling with color, you can notice some delays which are made by coming back from last istance to the first uncomplete istance.