Posts: 3,885
Threads: 174
Joined: Apr 2022
Reputation:
202
01-28-2023, 07:45 PM
(This post was last modified: 01-28-2023, 07:50 PM by bplus.)
For Dimster request, sorry couldn't find what I was recalling so we can go with this simple demo:
The sum of intergers 1 to 100, 3 ways:
Code: (Select All) _Title "Recursive replacement for Loop" ' b+ 2023-01-28
For i = 1 To 100 ' normal loop
tot = tot + i
Next
Print tot
i = 1: fini = 100 ' GoSub method
GoSub counting
Print totGOSUB
Dim Shared sum ' global sum for saving subtotals in for recCount Function
Print recCount(1, 100)
End
counting: ' recursive because it calls until i hits 100
totGOSUB = totGOSUB + i
If i < 100 Then i = i + 1: GoSub counting
Return
Function recCount (i, fini) ' recursive because it calls itself until i hits 100
sum = sum + i
If i < fini Then recCount = recCount(i + 1, fini) Else recCount = sum
End Function
EDIT: more comments
b = b + ...
Posts: 367
Threads: 54
Joined: Apr 2022
Reputation:
13
Thanks very much.
The recursion by Subroutine ... does it need to have the starting and ending value established before the call to the subroutine or can those values be within the subroutine itself? Also, does the Subroutine name require those double dots ( : ) after it's name?
Thanks again for this code.
Posts: 3,885
Threads: 174
Joined: Apr 2022
Reputation:
202
01-28-2023, 09:28 PM
(This post was last modified: 01-28-2023, 09:31 PM by bplus.)
Yes a GoSub routine does need double dots AKA a colon after the label name, well you might do it with a line number but yuck!
You could probably start a recursive routine with start value, easier with a Sub or Function than a GoSub, maybe?
Subs and Functions have a STATIC tool which would be handy for things like that.
It'd be tricky for GoSub because it has no private variables from main routine that contains it.
b = b + ...
Posts: 367
Threads: 54
Joined: Apr 2022
Reputation:
13
Ya, it's double dots for me, colon is too close to a body part but perhaps it is more appropriate as in "..we give our heart and sole and colon to coding". Has a ring to it.
Also, I was able to use the Select All feature to copy and paste your code - is that feature back or were you able to do something when placing it in your post to me?
And finally, I have an old computer tower which I have plans to throw out. Took a look for data to delete before I do and low and behold I found your two examples of Recursion by Subroutine and Recursion by Function. Boy oh Boy what a relief. Like finding a Rembrandt.
Posts: 3,885
Threads: 174
Joined: Apr 2022
Reputation:
202
01-29-2023, 04:23 PM
(This post was last modified: 01-29-2023, 04:24 PM by bplus.)
Hi @Dimster
The Select All feature is available to any poster putting their code (or text even) inside code tags when they are editing their post. (For some odd reason it does not work for you if you just posted it to forum, one of those weird glitches, maybe it figures you should already have the code as if it had a brain.)
You've got me curious what code was so memorable that you would compare it to a Rembrandt?
Would you mind posting?
b = b + ...
Posts: 367
Threads: 54
Joined: Apr 2022
Reputation:
13
Here is the example you provided for Recursion by Subroutine
Code: (Select All) '_Title "Recursion example" 'b+ 2021-10-27
_Title "Recursion example by Subroutine"
'Recursion is a sub or function that calls itself until it's job is done
'Here is a grahics
Const pi = _Pi
Screen _NewImage(700, 700, 32)
recThis 700 / 2, 700 / 2, 350 / 2, 1
Sub recThis (x, y, arm, level As Integer)
'first thing to ask in recursive subroutine is are we done!!!
If arm < 2 Then Exit Sub ' recursion is finished
' no not done
If level Mod 2 Then
x1 = x + arm * Cos(0): y1 = y + arm * Sin(0)
x2 = x + arm * Cos(pi): y2 = y + arm * Sin(pi)
Line (x1, y1)-(x2, y2)
Else
x1 = x + arm * Cos(pi / 2): y1 = y + arm * Sin(pi / 2)
x2 = x + arm * Cos(1.5 * pi): y2 = y + arm * Sin(1.5 * pi)
Line (x1, y1)-(x2, y2)
End If
recThis x1, y1, arm * .7, level + 1
recThis x2, y2, arm * .7, level + 1
End Sub
And here is your Recursion by Function
Code: (Select All) '_Title "Recursion example" 'b+ 2021-10-27
_Title "Recursion example by Function"
'Recursion is a sub or function that calls itself until it;s job is done
'Here is a text example
Const pi = _Pi
Screen _NewImage(700, 700, 32)
s$ = "This is an example of bplus using recursion to reverse this text."
Print s$
Print reverseMeSomeMore$(s$, 0)
Function reverseMeSomeMore$ (text$, level)
' are we there yet?
If level = Int(Len(text$) / 2) + 1 Then reverseMeSomeMore$ = text$: Exit Function
s$ = Mid$(text$, level, 1)
c$ = Mid$(text$, Len(text$) - level + 1, 1)
Mid$(text$, level, 1) = c$
Mid$(text$, Len(text$) - level + 1, 1) = s$
reverseMeSomeMore$ = reverseMeSomeMore$(text$, level + 1)
End Function
I actually hadn't thought that Recursion by Label was a thing.
Posts: 3,885
Threads: 174
Joined: Apr 2022
Reputation:
202
01-29-2023, 05:45 PM
(This post was last modified: 01-29-2023, 05:52 PM by bplus.)
+1 Thanks @Dimster
Those are beauties, I am saving them in my Basic Lectures Folder thanks again for reminders.
Quote:I actually hadn't thought that Recursion by Label was a thing.
You mean the GoSub ie GoSub (LineLabel)?
Yeah you have to be careful with global variables that are visible to main program, sometimes it's easier to keep instances of calls separate to keep the different values to a variable as you can inside a Sub or Function That is the work of the Stack that works behind the scenes tracking all the values a variable has in different calls to the same routine. Cool stuff!
b = b + ...
Posts: 367
Threads: 54
Joined: Apr 2022
Reputation:
13
About that STACK. Am I understanding it correctly that our Do Loops, For Loops and even Select Cases, are on and off the stack once the loops are completed, whereas Recursion keep piling onto the Stack to the point where is could over flow the stack. If that's correct, is there a code that can be included with Recursive code that monitors the condition of the stack?
Posts: 3,885
Threads: 174
Joined: Apr 2022
Reputation:
202
(01-30-2023, 05:36 PM)Dimster Wrote: About that STACK. Am I understanding it correctly that our Do Loops, For Loops and even Select Cases, are on and off the stack once the loops are completed, whereas Recursion keep piling onto the Stack to the point where is could over flow the stack. If that's correct, is there a code that can be included with Recursive code that monitors the condition of the stack?
Don't need a stack to track where, which line to jump execution to in loop, nor in select case or If Then ElseIF... Then Else end if. Those are just GOTO's in deisguise.
Stacks do track calls to Subs and functions and the variable values meant to be private to that particular call. Last In First Out.
b = b + ...
Posts: 2,673
Threads: 325
Joined: Apr 2022
Reputation:
214
(01-30-2023, 05:36 PM)Dimster Wrote: About that STACK. Am I understanding it correctly that our Do Loops, For Loops and even Select Cases, are on and off the stack once the loops are completed, whereas Recursion keep piling onto the Stack to the point where is could over flow the stack. If that's correct, is there a code that can be included with Recursive code that monitors the condition of the stack?
QB64 doesn't really use stackspace like QB45 did. Instead, we basically use a resizable array to store where we need to return back to, so as long as your PC has memory left, you're not going to run out of stack space. Think of the process as this:
GOSUB foo --- this does the basic following:
1) Create an internal label for Return_From_foo directly after this GOSUB. This gives us a point to return back from.
2) Check an internal array for return labels. Normally it holds XXX number of entries. If there's already XXX entries in the array, it resizes it to hold XXX + YYY entries.
3) Increment our current array index by 1. return_index = return_index +1
4) Store this label in the array. Return_Array(return_index) = "Return_From_foo".
5) GOTO foo
Now, when we run our code and come to a RETURN statement, it basically does the following:
1) Look at the last array element. Lookup Return_Array(return_index).
2) GOTO that internal label.
3) reduce return_index by 1. return_index = return_index -1
This gives us a jump point and a return point, and works on a basic FILO principal.
As long as you have memory for that internal array to keep growing and increasing its size, your program isn't going to crash like it used to do back in QB45.
|