Recursion: 4 ways to get it working

[TempodiBasic]

Hi
I think that this demo is clear enough to be used as example about recursion in QB64pe.

I must remark that the STATIC way has is goal in preserving the previouse values of variable of the SUB/FUNCTION.
So if we need to preserve  few variables we can use STATIC into the SUB to declare the variable to preserve,
instead if we need to preserve all variable or the more part  of local variables we use STATIC in SUB/FUNCTION declaration.

Code: (Select All)

Rem Demonstration of variables into recursive calling
Screen 0
Dim counter As Single
Dim Shared counter2 As Single
Dim Choice As String

Choice = " "
Do
    If Choice <> "" Then
        Cls
        Print "we are testing recursive calling"
        Print String$(60, "#")
        Print "please make your choice: "
        Print " press 1 for recursion without parameter or shared variable"
        Print " press 2 for recursion with parameter and no shared variable"
        Print " press 3 for recursion with shared variable and no parameter"
        Print " press 4 for STATIC recursion without parameter or shared variable"
        Print " press 0 to exit from demonstration"
        Print String$(60, "#")
    End If
    Choice = InKey$
    If Choice = "0" GoTo Ending
    If Choice = "1" Then GoSub NoParameters
    If Choice = "2" Then GoSub YesParameters
    If Choice = "3" Then GoSub SharedVariable
    If Choice = "4" Then GoSub StaticNoParameters
Loop
End

NoParameters:
counter = 0
Print " No parameter and no shared variable demo"
Print "-----------------------------------------"
Print counter; " value of flag in the main"
RecursiveNoParameters
Return

YesParameters:
counter = 0
Print " Yes parameter and no shared variable demo"
Print "------------------------------------------"
Print counter; " value of flag in the main"
RecursiveYesParameters counter
Return

SharedVariable:
counter2 = 0
Print " No parameter and Yes shared variable demo"
Print "------------------------------------------"
Print counter2; " value of flag in the main"
SharedVariables
Return

StaticNoParameters:
counter = 0
Print " STATIC and no parameter and no shared variable demo"
Print "-----------------------------------------"
Print counter; " value of flag in the main"
StaticNoParameter
Return

Ending:
Rem here the flow of code ends
End


Sub RecursiveNoParameters
    counter = counter + 1
    DoJob counter
    If InKey$ <> "" Then Exit Sub ' emergency exit
    If counter < 10 Then RecursiveNoParameters
End Sub

Sub RecursiveYesParameters (c As Single)
    c = c + 1
    DoJob c
    If InKey$ <> "" Then Exit Sub ' emergency exit
    If c < 10 Then RecursiveYesParameters c
End Sub

Sub SharedVariables
    counter2 = counter2 + 1
    DoJob counter2
    If InKey$ <> "" Then Exit Sub ' emergency exit
    If counter2 < 10 Then SharedVariables
End Sub

Sub StaticNoParameter
    Static counter ' you need to have STATIC only the flag of recursion, at least
    counter = counter + 1
    DoJob counter
    If InKey$ <> "" Then Exit Sub ' emergency exit
    If counter < 10 Then StaticNoParameter
End Sub


Sub DoJob (c As Single)
    Print c; " press a key to stop the recursive loop"
    Sleep 1 ' we need this to avoid the crash of application
End Sub

more explanation and tips coming soon.

[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.

[Dimster]

Hi Tempodi ... I think I've learned more on Recursion in BASIC in this past month than the past year trying to decipher Recursion from the internet. If the speed between Iteration and Recursion is fairly equal with present day computer power, then it's the depth (how many matriosca's) iteration can perform more than recursion. Of the 4 recursion methods demonstrated, is there one which may have more depth to it than another?

[Dimster]

My apologies Tempodi - it's not DEPTH I meant but STACKed. Iteration is depth to me as to how many wooden dolls can be fit into one another. That's what depth is to me. But recursion can't do that, recursion can be stacked on recursion call on top of another. My question is, is there one Recursion type you have demonstrated better than another for Stacking?

[TempodiBasic]

My apologies Tempodi - it's not DEPTH I meant but STACKed. Iteration is depth to me as to how many wooden dolls can be fit into one another. That's what depth is to me. But recursion can't do that, recursion can be stacked on recursion call on top of another. My question is, is there one Recursion type you have demonstrated better than another for Stacking?

Hi Dimster
as already SMcNeill said :" It is the amount of available RAM to define how many recursion is possible to do until we get Overflow.
Going to analyze the different methods of recursion...

1. recursive calling a SUB with parameter as flag  

2. recursive calling a SUB with Global Shared variable as flag or a Shared variable between main and SUB recursive

3. recursive calling a SUB with STATIC option to preserve local variable as flag or a STATIC group of variables

we must answer to these questions to be able to answer to your is there one Recursion type you have demonstrated better than another for Stacking?

Is there a difference in speed of access to the variable if it is a parameter of SUB or a Global Shared variable or a SHARED variable or  a STATIC variable?
Is there a difference in amount of RAM used using these different methods? Otherwise a parameter vs global shared vs shared vs STATIC local variable does use different quantity of RAM?
Well, I think that these features depend on the architecture of compiler/interpreter and how it works with stack. 
In this point of view , for QB64pe the answer can arrive from developers of QB64pe.

[bplus]

Fractals work great with recursion! I could do an art show!

[TempodiBasic]

Fractals work great with recursion! I could do an art show!

 I hope you'll do as soon you can. It is very beautiful to see the facts over the teoretic moment.

[bplus]

Fractals work great with recursion! I could do an art show!

 I hope you'll do as soon you can. It is very beautiful to see the facts over the teoretic moment.

 A quickie from Proggies:

Code: (Select All)

_Title "Flower Wheel" ' b+ 2022-04?
Screen 12
Do
    Cls
    o = o + _Pi / 180
    drawc _Width / 2, _Height / 2, _Width / 5, .25, 4, o
    _Display
    _Limit 30
Loop

Sub drawc (x, y, r, a, n, o)
    If n > 0 Then
        For t = 0 To _Pi(2) Step _Pi(1 / 3)
            xx = x + r * Cos(t + o)
            yy = y + r * Sin(t + o)
            Circle (xx, yy), r
            drawc xx, yy, a * r, a, n - 1, -o - n * _Pi / 180
        Next
    End If
End Sub

[TempodiBasic]

Fractals work great with recursion! I could do an art show!

 I hope you'll do as soon you can. It is very beautiful to see the facts over the teoretic moment.

 A quickie from Proggies:

Code: (Select All)

_Title "Flower Wheel" ' b+ 2022-04?
Screen 12
Do
    Cls
    o = o + _Pi / 180
    drawc _Width / 2, _Height / 2, _Width / 5, .25, 4, o
    _Display
    _Limit 30
Loop

Sub drawc (x, y, r, a, n, o)
    If n > 0 Then
        For t = 0 To _Pi(2) Step _Pi(1 / 3)
            xx = x + r * Cos(t + o)
            yy = y + r * Sin(t + o)
            Circle (xx, yy), r
            drawc xx, yy, a * r, a, n - 1, -o - n * _Pi / 180
        Next
    End If
End Sub

fine graphic, please post more or a collection of yours snippets when you can!






this is my first simple tribute to do graphic with recursion: a chesstable maker

Code: (Select All)

' recursive demo drawing a chesstable
Screen _NewImage(1000, 1000, 32)
_ScreenMove 1, 1
_Title "Chess table recursive way"

Cls , _RGB32(6, 6, 230)
cell 1, 1
End

Sub cell (x As Integer, y As Integer)
    'x is the counter of cells into the row
    ' y is the counter of rows into the table
    Dim c As Long
    If (x + y) Mod 2 = 0 Then
        c = _RGB32(255)
    Else
        c = _RGB32(0)
    End If

    Line (100 * x, 100 * y)-Step(100, 100), c, BF
    _Delay .05
    If (x + y) < 64 Then
        If x < 8 Then
            x = x + 1
        Else
            x = 1
            If y < 8 Then y = y + 1 Else Exit Sub
        End If
        cell x, y
    Else
        Exit Sub
    End If
End Sub

[TempodiBasic]

@Bplus
if you remember this, here its recursive way

Code: (Select All)

Option _Explicit

Const White = _RGB32(255), Black = _RGB32(0), Gray = _RGB32(100), Wscreen = 400, Hscreen = 400
Dim As Single Wsquare, Hsquare, Repeat, Left, Sum
Screen _NewImage(Wscreen, Hscreen, 32)
_Title "Shrinked chess pattern recursive way"
Cls , Gray
Wsquare = Wscreen / 2
Hsquare = Hscreen / 2
Repeat = 1
Sum = 0
Left = 0
pattern Wsquare, Hsquare, Repeat, Sum, Left
End

Sub pattern (Wsquare, Hsquare, Repeat, Sum, Left)
    If Sum >= Wscreen Then Exit Sub
    Dim a As Integer
    Dim Top
    _Delay .2
    For a = 1 To Repeat
        Line (Left, Top + (Hsquare * (a - 1)))-(Left + Wsquare, Top + (Hsquare * a)), White, BF
        Line (Left, Top + (Hsquare * a))-(Left + Wsquare, Top + (Hsquare * (a + 1))), Black, BF
        Top = Top + Hsquare
    Next a
    Repeat = Repeat * 2
    Left = Left + Wsquare
    Wsquare = Wsquare / 2
    Hsquare = Hsquare / 2
    Sum = Sum + Wsquare
    Call pattern(Wsquare, Hsquare, Repeat, Sum, Left)
End Sub