Text Only | Text with Attachments

QB64.org Forum

Active Forums => QB64 Discussion => Topic started by: Dimster on March 14, 2022, 10:40:37 am

Title: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: Dimster on March 14, 2022, 10:40:37 am
I have a number of nested for loops and do loop and was thinking of changing some of them into recursive statements by changing the outer loop to a subroutine that is called in the inner do loop. Not sure if I have explained that right but here is an example of the format. Main problem (actually the first problem I am encountering) is stopping the recursion.

Code: QB64: [Select]
  2.     a = 0
  3.     b = b + 1
  4.  
  5.     DO
  6.         a = a + 1
  7.         PRINT " Value of A is "; a; "  Value of B is "; b
  8.  
  9.     LOOP UNTIL a = 100
  10. LOOP UNTIL b = 100
  12.  
  13.  
  15.     a = a + 1
  16.     PRINT " Value of A is "; a; "  Value of C is "; c
  17.     desub
  19.  
  20.  
  21.  
  22.  
  23. SUB desub
  24.     a = 0
  25.     c = c + 1
  26.     IF c = 100 THEN SLEEP
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: mdijkens on March 14, 2022, 10:50:39 am
I'm not really seeing any recursion pattern in this example

The first one runs through a 'matrix' b,a which is fine (could also be done with 2 nested for-loops)
The second one runs a=1,c=[0,=>] and pauses at a=1,c=100

recursion is mostly evident when you want to do something with a piece of data/sequence and then do the same processing on the remaining part of the data/sequence
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: bplus on March 14, 2022, 11:12:28 am
to 100 or to 10 doesn't matter unless you want to see b more than just last number:
Code: QB64: [Select]
  2.     a = 0
  3.     b = b + 1
  4.     recA a + 1, b  ' edit: a to a + 1
  5.     'Do
  6.     '    a = a + 1
  7.     '    Print " Value of A is "; a; "  Value of B is "; b
  8.  
  9.     'Loop Until a = 10
  10. Loop Until b = 10
  12.  
  13. Sub recA (a, b)
  14.     Print " Value of A is "; a; "  Value of B is "; b
  15.     If a = 10 Then Exit Sub Else recA a + 1, b

A recursive sub needs to know when to quit just like a loop.
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: bplus on March 14, 2022, 11:28:25 am
Here's the other loop too:
Code: QB64: [Select]
  1. recB 0, 0
  2. 'Do
  3. '    a = 0
  4. '    b = b + 1
  5. '    recA a + 1, b
  6. '    'Do
  7. '    '    a = a + 1
  8. '    '    Print " Value of A is "; a; "  Value of B is "; b
  9.  
  10. '    'Loop Until a = 10
  11. 'Loop Until b = 10
  13.  
  14. Sub recA (a, b)
  15.     Print " Value of A is "; a; "  Value of B is "; b
  16.     If a = 10 Then Exit Sub Else recA a + 1, b
  18.  
  19. Sub recB (a, b)
  20.     a = 1: b = b + 1
  21.     If b <= 10 Then recA a, b: recB a, b
  23.  
  24.  
  25.  

Well that was fun! Thankyou for the question on recursion.

I agree with @mdijkens, recursion is typically used for something trickier than a simple loop.
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: Dimster on March 14, 2022, 01:48:39 pm
@mdijkens - yes, that was a poor over simplification of nested Do Loops. The meaning and use of recursion I do understand and agree with  your definition.

@bplus - thanks for your example. So it would appear each Do Loop would need it's own Subroutine. (There would be no Do Loop at all).And each Recursive subroutine would then call the other with stop value in just one of the Recursive Subroutines.

I've been trying to place a Do Loop within a recursive Subroutine and placing the stop value within the same recursive Subroutine. I was thinking the stop value may need to be in the Do Loop itself rather than the recursive subroutine. But....seems recursion best lives in a subroutine and not meant be associate with Do Loops.

Thanks Guys
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: bplus on March 14, 2022, 02:24:53 pm
Quote from: Dimster on March 14, 2022, 01:48:39 pm
@mdijkens - yes, that was a poor over simplification of nested Do Loops. The meaning and use of recursion I do understand and agree with  your definition.

@bplus - thanks for your example. So it would appear each Do Loop would need it's own Subroutine. (There would be no Do Loop at all).And each Recursive subroutine would then call the other with stop value in just one of the Recursive Subroutines.

I've been trying to place a Do Loop within a recursive Subroutine and placing the stop value within the same recursive Subroutine. I was thinking the stop value may need to be in the Do Loop itself rather than the recursive subroutine. But....seems recursion best lives in a subroutine and not meant be associate with Do Loops.

Thanks Guys


 "So it would appear each Do Loop would need it's own Subroutine."
Yeah, each recursive function probably does replace a loop at least.

"And each Recursive subroutine would then call the other with stop value in just one of the Recursive Subroutines."
Not in the above. RecA only calls itself and RecB calls RecA until it's finished and then calls itself until it's finished. Each contains their own stop and exit value.

It would be a very interesting thing to see each recursive routine call the other!

"I've been trying to place a Do Loop within a recursive Subroutine and placing the stop value within the same recursive Subroutine."
That would make things loopy, again recursive routines usually replace loops.
But placing stop value in same recursive sub is safer than depending on another sub specially a recursive one..

Here's another version of the above code:
Code: QB64: [Select]
  2. a = 0: b = 0
  3. recB
  5.  
  6. Sub recA  ' recA only calls itself
  7.     Print " Value of A is "; a; "  Value of B is "; b
  8.     a = a + 1: If a > 10 Then Exit Sub Else recA
  10.  
  11. Sub recB 'recB calls recA and waits until recA is done before it calls itself again and only if b is under stop value.
  12.     _Delay 1
  13.     a = 1: b = b + 1: If b <= 10 Then recA: recB
  15.  
  16.  
  17.  
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: Dimster on March 14, 2022, 03:43:41 pm
I realize you can't nest one subroutine in another but you would think one recursive subroutine calling the other would be a form of recursive nesting wouldn't it? Like a Quick Sort within a Quick Sort. I suppose the theory is one thing but the practice is to run each recursive subroutine to their logical end. I like nesting in AI programming. Nested Do Loops can accomplish a lot especially paired with If statements and Select Cases. It would be lovely to add recursive to the Looping arsenal.
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: SMcNeill on March 14, 2022, 03:49:47 pm
Quote from: Dimster on March 14, 2022, 01:48:39 pm
I've been trying to place a Do Loop within a recursive Subroutine and placing the stop value within the same recursive Subroutine. I was thinking the stop value may need to be in the Do Loop itself rather than the recursive subroutine. But....seems recursion best lives in a subroutine and not meant be associate with Do Loops.

Thanks Guys

There's no issues with a DO.. LOOP being in a recursive sub.  Take the following as an example, based on your original main loop:

Code: QB64: [Select]
  1. RecursiveMain 0, 100
  2.  
  3. Sub RecursiveMain (b, bLimit)
  4.     b = b + 1
  5.     Do
  6.         a = a + 1
  7.         Print " Value of A is "; a; "  Value of B is "; b
  8.     Loop Until a = 100
  9.     Sleep
  10.     If b <> bLimit Then RecursiveMain b, bLimit

You just need to choose the point where you want the recursion to occur at; there's no issues at all with having DO..FOR..WHILE.. or any other keyword inside your recursive looping.

The real question is: WHY would you want recursion when you don't need it?  It eats up stack space, has a tendency to overload and crash programs when used excessively, and isn't honestly any faster or more efficient.  Personally, I'd much rather be working with the original code than trying to wrap my brain around what's going on with the recursive routines.  It's not that I can't sort them out and understand them; it's that I can't sort them out and understand them as easily as I can with a simple DO... LOOP.

Maybe that's just me, but anytime recursion is used, I have to take a moment to sit back and visualize and sort out what's going on when I see a function call itself.  It just adds to the complexity of things, and if I can get by without having to use it in my stuff, generally speaking that's what I try and do. 
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: Dimster on March 14, 2022, 04:25:38 pm
Food for thought Steve...Multiple nesting can be difficult to follow the action as well but I was thinking recursion maybe faster than a Do Loop with a high loop control value. Of course I have never been able to get it off the ground to see if there is any speed or accuracy advantage.
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: bplus on March 14, 2022, 05:13:49 pm
I am with Steve, don't use recursive routines unless they make things easier to code and understand. Certainly not to merely replace Do Loops with a sub procedure.
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: tomxp411 on March 14, 2022, 07:09:52 pm
Right, this is clearly not a good candidate for a recursive algorithm. Recursion is ideal for walking any sort of tree structure, since you can walk down each branch without losing track of where you started. When dealing with gaming, it's also ideal for pathfinding algorithms. Dijkstra's algorithm, for example, is the fundamental algorithm used in graph theory, and it's all about recursion. Each node is tested recursively, and the recursion terminates when a path reaches a terminal point (the goal or a dead end).

However, the classic example for recursion is reading a directory tree:

(this is psuedocode, not VB):

sub GetDirectory(path)
    Read Directory into directory()
    for each entry in directory()
        print entry
        if entry is directory then GetDirectory(entry)
    next
end sub




Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: bplus on March 14, 2022, 07:18:50 pm
Sure and don't forget drawing trees!
Code: QB64: [Select]
  1. _Title "Basic Tree from branch"
  3. Screen _NewImage(800, 600, 32)
  4. _ScreenMove 300, 20
  5. Color _RGB32(0, 255, 0)
  6.  
  7. 'just test call to sub
  8. '       x,   y,  270, .2*height, 1  start a tree with 270 degrees to point up, and about 1/5 the height you want to grow the tree
  9. branch 400, 500, 270, 100, 1
  10. Print "press any to see the forest..."
  12.  
  13. horizon = .35 * _Height
  14. For i = 0 To horizon
  15.     Line (0, i)-(_Width, i), _RGB(0, 0, .25 * i + 100)
  17. For i = horizon To _Height
  18.     Line (0, i)-(_Width, i), _RGB(0, 255 - .25 * i - 50, 0)
  20. For i = 1 To 250
  21.     y = randWeight(horizon, _Height, 3)
  22.     branch _Width * Rnd, y, 270, (.015 * Rnd + .027) * y, 1
  25.  
  26. Sub branch (x, y, angD, lngth, lev)
  27.     x2 = x + Cos(_D2R(angD)) * lngth
  28.     y2 = y + Sin(_D2R(angD)) * lngth
  29.     Line (x, y)-(x2, y2), _RGB32(Rnd * 100, Rnd * 170 + 80, Rnd * 50)
  30.     If lev > 6 Or lngth < 2 Then Exit Sub
  31.     l = lev + 1
  32.     branch x2, y2, angD + 10 + 30 * Rnd, .7 * lngth + .2 * Rnd * lngth, l
  33.     branch x2, y2, angD - 10 - 30 * Rnd, .7 * lngth + .2 * Rnd * lngth, l
  34.     If Rnd < .65 Then branch x2, y2, angD + 20 * Rnd - 10, .7 * lngth + .2 * Rnd * lngth, l
  36.  
  37. Function randWeight (manyValue, fewValue, power)
  38.     randWeight = manyValue + Rnd ^ power * (fewValue - manyValue)
  40.  
  41.  
  42.  

  [ This attachment cannot be displayed inline in 'Print Page' view ]  
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: wiggins on March 15, 2022, 09:26:19 pm
The trees look great !!!
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: Pete on March 16, 2022, 11:05:13 pm
Couldn't leaf well enough alone, could you?

Pete
Title: Re: How do you convert a nested Do Loop into a recursive subroutine call?
Post by: _vince on March 17, 2022, 08:06:05 pm
Quote from: Pete on March 16, 2022, 11:05:13 pm
Couldn't leaf well enough alone, could you?

had to highlight that in bold for us slow wits?
Text Only | Text with Attachments