How do you convert a nested Do Loop into a recursive subroutine call?

[Dimster]

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]

1. DO
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
11. SLEEP
12.  
13.  
14. DO
15.     a = a + 1
16.     PRINT " Value of A is "; a; "  Value of C is "; c
17.     desub
18. LOOP
19.  
20.  
21.  
22.  
23. SUB desub
24.     a = 0
25.     c = c + 1
26.     IF c = 100 THEN SLEEP
27. END SUB

[mdijkens]

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

[bplus]

to 100 or to 10 doesn't matter unless you want to see b more than just last number:

Code: QB64: [Select]

1. Do
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
11. Sleep
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
16. End Sub

A recursive sub needs to know when to quit just like a loop.

[bplus]

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
12. Sleep
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
17. End Sub
18.  
19. Sub recB (a, b)
20.     a = 1: b = b + 1
21.     If b <= 10 Then recA a, b: recB a, b
22. End Sub
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.

[Dimster]

@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

[bplus]

@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]

1. Dim Shared As Integer a, b
2. a = 0: b = 0
3. recB
4. Sleep
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
9. End Sub
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
14. End Sub
15.  
16.  
17.  

[Dimster]

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.

[SMcNeill]

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
11. End Sub

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. 

[Dimster]

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.

[bplus]

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.

[tomxp411]

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

[bplus]

Sure and don't forget drawing trees!

Code: QB64: [Select]

1. _Title "Basic Tree from branch"
2. Randomize Timer
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..."
11. Sleep
12.  
13. horizon = .35 * _Height
14. For i = 0 To horizon
15.     Line (0, i)-(_Width, i), _RGB(0, 0, .25 * i + 100)
16. Next
17. For i = horizon To _Height
18.     Line (0, i)-(_Width, i), _RGB(0, 255 - .25 * i - 50, 0)
19. Next
20. For i = 1 To 250
21.     y = randWeight(horizon, _Height, 3)
22.     branch _Width * Rnd, y, 270, (.015 * Rnd + .027) * y, 1
23. Next
24. Sleep
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
35. End Sub
36.  
37. Function randWeight (manyValue, fewValue, power)
38.     randWeight = manyValue + Rnd ^ power * (fewValue - manyValue)
39. End Function
40.  
41.  
42.  

  [ You are not allowed to view this attachment ]  

[wiggins]

The trees look great !!!

[Pete]

Couldn't leaf well enough alone, could you?

Pete

[_vince]

Couldn't leaf well enough alone, could you?

had to highlight that in bold for us slow wits?