Recursion: 4 ways to get it working

Recursion: 4 ways to get it working - Printable Version

+- QB64 Phoenix Edition (https://qb64phoenix.com/forum)
+-- Forum: QB64 Rising (https://qb64phoenix.com/forum/forumdisplay.php?fid=1)
+--- Forum: Code and Stuff (https://qb64phoenix.com/forum/forumdisplay.php?fid=3)
+---- Forum: Help Me! (https://qb64phoenix.com/forum/forumdisplay.php?fid=10)
+---- Thread: Recursion: 4 ways to get it working (/showthread.php?tid=1473)

Pages: 1 2

Recursion: 4 ways to get it working - TempodiBasic - 02-14-2023

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.

RE: Recursion: 4 way to get it working - TempodiBasic - 02-14-2023

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.

RE: Recursion: 4 ways to get it working - Dimster - 02-14-2023

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?

RE: Recursion: 4 ways to get it working - Dimster - 02-14-2023

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?

RE: Recursion: 4 ways to get it working - TempodiBasic - 02-14-2023

(02-14-2023, 09:13 PM)Dimster Wrote: 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.

RE: Recursion: 4 ways to get it working - bplus - 02-14-2023

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

RE: Recursion: 4 ways to get it working - TempodiBasic - 02-15-2023

(02-14-2023, 11:54 PM)bplus Wrote: 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.

RE: Recursion: 4 ways to get it working - bplus - 02-15-2023

(02-15-2023, 12:13 AM)TempodiBasic Wrote:
(02-14-2023, 11:54 PM)bplus Wrote: 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

RE: Recursion: 4 ways to get it working - TempodiBasic - 02-17-2023

(02-15-2023, 02:10 AM)bplus Wrote:
(02-15-2023, 12:13 AM)TempodiBasic Wrote:
(02-14-2023, 11:54 PM)bplus Wrote: 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!

[Image: immagine-2023-02-17-105041253.png]

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

RE: Recursion: 4 ways to get it working - TempodiBasic - 02-17-2023

@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