Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Loops alternate recursive ways
#1
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 + ...
Reply
#2
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.
Reply
#3
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 + ...
Reply
#4
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.
Reply
#5
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 + ...
Reply
#6
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.
Reply
#7
Thumbs Up 
+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 + ...
Reply
#8
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?
Reply
#9
(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 + ...
Reply
#10
(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.
Reply




Users browsing this thread: 2 Guest(s)