Recursion

[Dimster]

I was wondering if I could get your advice on where best to apply recursive code. Now that Function has a recursive element to it, would it be to my speed advantage to explore it? I presently have in my program multiple calls to the same Subroutine. Basically the program inputs data, calls a subroutine to work with the data then onto the next piece of data. I was thinking perhaps the program may have speed advantage if it inputted and stored the data, then, once I have it all,  use a recursive function call to perform the same work on each piece of data which the Subroutine had been performing. This is the trouble with new toys...your imagination goes wild and reality is always so painfully down the road.

[FellippeHeitor]

Not answering your question, but just to clarify: recursion is not new in QB64. One specific scenario of functions without parameters failing to call themselves has been fixed in v2.

[FellippeHeitor]

And some examples of recursive functions for you to be inspired: http://www.qb64.org/wiki/STATIC

[Dimster]

Thanks Fell ... yes, I was aware V2.0 fixed that specific instance in Functions. I have always looked to Subroutines to do the heavy lifting and Functions to do quick math or handling Scientific Notation. When you were explaining the fix to Functions it occurred to me that Functions could do a lot more of the heavy lifting but why do it if there isn't some kind of an advantage....and thanks a lot for the "Static" . I must admit that really does give my perception of how functional functions can be.

[bplus]

Here's a graphics example of recursion:

Code: QB64: [Select]

1. _Title "Recursion example" 'b+ 2021-10-27
2.  
3. 'Recursion is a sub or function that calls itself until it's job is done
4. 'Here is a grahics
5. Const pi = _Pi
6. Screen _NewImage(700, 700, 32)
7.  
8. recThis 700 / 2, 700 / 2, 350 / 2, 1
9.  
10. Sub recThis (x, y, arm, level As Integer)
11.     'first thing to ask in recursive subroutine is are we done!!!
12.     If arm < 2 Then Exit Sub ' recursion is finished
13.     ' no not done
14.     If level Mod 2 Then
15.         x1 = x + arm * Cos(0): y1 = y + arm * Sin(0)
16.         x2 = x + arm * Cos(pi): y2 = y + arm * Sin(pi)
17.         Line (x1, y1)-(x2, y2)
18.     Else
19.         x1 = x + arm * Cos(pi / 2): y1 = y + arm * Sin(pi / 2)
20.         x2 = x + arm * Cos(1.5 * pi): y2 = y + arm * Sin(1.5 * pi)
21.         Line (x1, y1)-(x2, y2)
22.     End If
23.     recThis x1, y1, arm * .7, level + 1
24.     recThis x2, y2, arm * .7, level + 1
25. End Sub
26.  

[bplus]

I think this is an example of recursion making things more complicated to reverse some text:

Code: QB64: [Select]

1. _Title "Recursion example" 'b+ 2021-10-27
2.  
3. 'Recursion is a sub or function that calls itself until it;s job is done
4. 'Here is a text example
5. Const pi = _Pi
6. Screen _NewImage(700, 700, 32)
7. s$ = "This is an example of bplus using recursion to reverse this text."
8. Print s$
9. Print reverseMeSomeMore$(s$, 0)
10.  
11. Function reverseMeSomeMore$ (text$, level)
12.     ' are we there yet?
13.     If level = Int(Len(text$) / 2) + 1 Then reverseMeSomeMore$ = text$: Exit Function
14.     s$ = Mid$(text$, level, 1)
15.     c$ = Mid$(text$, Len(text$) - level + 1, 1)
16.     Mid$(text$, level, 1) = c$
17.     Mid$(text$, Len(text$) - level + 1, 1) = s$
18.     reverseMeSomeMore$ = reverseMeSomeMore$(text$, level + 1)
19. End Function
20.  
21.  

[Dimster]

So do you have preference? They are short examples but I felt the Subroutine ran a little faster than the Function..then again the function had to deal with strings

[Dimster]

Thanks for the examples by the way. I am loosely defining Recursion as just multiple calls. So I've looking at this from the perspective of calling the same subroutine from the main program. You've some very good example of recursive calls within the Subroutine and Function. I have never really approached recursion within the routine but that recursion within the Function is what I have been thinking of doing.

Also would appear, in terms of speed.... I should be considering the time involved in multiple calls from the main program to the same subroutine  v's recursive calls within a Function. (not exactly sure how to re-code the program to do this) But I'm thinking one call to the Function may in fact be faster.

[bplus]

So do you have preference? They are short examples but I felt the Subroutine ran a little faster than the Function..then again the function had to deal with strings

It really depends on what you are trying to do.
I can't imagine drawing some things without recursion eg, trees, who wants to have to keep track of all the branching?

I've also used it for Sudoku solutions and MineSweeper for sweeping empty cells and for Paint3 that paints one color when it finds another color. Qsort uses recursion.

The Classic example of recursion is factorial but I would just use a loop for that. Recursion is cool when it splits one call to 2 or 4 for 2D work like first example above.

Oh you @Dimster posted while I was answering previous.

[bplus]

Thanks for the examples by the way. I am loosely defining Recursion as just multiple calls. So I've looking at this from the perspective of calling the same subroutine from the main program. You've some very good example of recursive calls within the Subroutine and Function. I have never really approached recursion within the routine but that recursion within the Function is what I have been thinking of doing.

Also would appear, in terms of speed.... I should be considering the time involved in multiple calls from the main program to the same subroutine  v's recursive calls within a Function. (not exactly sure how to re-code the program to do this) But I'm thinking one call to the Function may in fact be faster.

The very definition of a recursive function or sub is that it calls itself to do it's job. It must call itself at least once to be considered recursive. It's like a code echo. :) Hey that gives me an idea!

[Dimster]

Wondering if I have this straight .. There is a danger with a Recursive procedure to cause a Stack Overflow. The solution is to use Static variables. I see where the recursive Quick Sort does not use Static variables (at least I have never declared Static variables when I use the Quick Sort method). So I'm thinking, if I create a Recursive procedure whereby a math formula is deployed (+,-,*,/) then this is were the danger lays. If the Recursion is simple comparisons, or True/False, or re-ordering then there is no threat to Overflow the Stack. Is that correct?

[bplus]

One thing that will save resources in a recursive QuickSort is to share the array and only work on that one specific array with the QuickSort routine, in that way it does not have to be an argument in the call to the sub and thus repeatedly called down the recursive line. In my Interpreter with Sorting, I think I copied arrays to standard shared array worked on by QuickSort routines. I even had different routines for ascending and descending so that would not have to be included in parameter list of the call to the specialized QuickSort routine.

What might surely blow the stack are recursive routines that have allot of parameters and branch out over seemingly endless lines of recursion.

The solution is to use Static variables.

Don't know about that, my instinct would would be to Share the variable and give it a name not likely to be used elsewhere.

[luke]

Wondering if I have this straight .. There is a danger with a Recursive procedure to cause a Stack Overflow. The solution is to use Static variables. I see where the recursive Quick Sort does not use Static variables (at least I have never declared Static variables when I use the Quick Sort method). So I'm thinking, if I create a Recursive procedure whereby a math formula is deployed (+,-,*,/) then this is were the danger lays. If the Recursion is simple comparisons, or True/False, or re-ordering then there is no threat to Overflow the Stack. Is that correct?

I think it's worth explaining exactly what a stack overflow is and why it occurs:

Every time the CPU jumps to a subroutine (a SUB or a FUNCTION), it needs to remember where in the code it came from, so it can go back there when it's finished.

The way it does this is by pushing its current address to the stack before jumping. But really, you can think of this as just having a big array in memory, and every time you need to do a subroutine you REDIM _PRESERVE the array to increase the size by one, add your current code position to the new element, then go to the subroutine. After you finish and return to where you came from, you can REDIM the array again to make it one element smaller (since you don't need the value any more).

Now, because of Reasons™ the program can only make this array so big, about 8MB in the best of cases (it could be quite a bit less). This means you can only have so many subroutines-that-call-subroutine, because eventually you'll run out of space to store these return locations. Note that this isn't a limit on the total number of subroutine calls we can make in the program in total, because whenever a subroutine returns it frees up an element of our array. It's just a limit on how many calls you can have chained together.

For further Reasons™ the data structure used to store these return locations is in fact a stack, and if it gets full it goes beyond its bounds, hence a "stack overflow" (in the real world the stack also grows downwards so the visual metaphor is a little messed up, but ignore that).

You can see now why recursion can be problematic - it's a very quick way to make many subroutine calls and fill up the stack with return locations. It doesn't matter what you're doing in the subroutine, if you're recursing you just have to make sure you have a limit on how deep the recursion goes.

Now, it turns out the exact number of recursive calls you can make is somewhat dependent on the contents of the routine: for even more Reasons™ every variable in a subroutine (that isn't SHARED, STATIC or a parameter) also takes up an element in the same stack that stores our return locations, and does so on every call. But don't be misled - even a subroutine with no local variables can cause a stack overflow, you just might have to wait a microsecond longer for it to happen.

It can be shown (by some high-pants maths) that every recursive program can actually be written as a nonrecursive one by using one or more loops. Rewriting it to remove the recursion is generally the way to go if you're having stack overflows (and it's not just a bug in your algorithm).

[Dimster]

So can a Stack Overflow be trapped or monitored?

[bplus]

Just like any error I suppose.