Recursion

[TempodiBasic]

Hi boys
IMHO
the amount of available resources and the amount of data to be processed are the compass to choose between recursive function and non-recursive algorithm.
Great resources and / or little amount of data are a good index for recursive function and vice versa.
Usually I have found recursion method used for binary search ,  algorythms of ordering (sorting data),  parsing algorythm (interpreter/compiler/syntax checker), translation algorythm, ripetitive calculation (factorial numbers, math sequence like Fibonacci, Collatz conjecture).
just my two cents

Happy coding

[SMcNeill]

If you want the easiest example of recursion, then I'd like to add in a simple Fill routine for folks to study:

Code: QB64: [Select]

1. Screen _NewImage(640, 480, 32)
2.  
3. Circle (240, 240), 200, &HFFFF0000
4. Fill 240, 240, &HFFFF0000
5.  
6. Sub Fill (x, y, kolor As _Unsigned Long)
7.     If Point(x, y) <> kolor Then Pset (x, y), kolor
8.     If Point(x + 1, y) <> kolor Then Fill x + 1, y, kolor
9.     If Point(x - 1, y) <> kolor Then Fill x - 1, y, kolor
10.     If Point(x, y + 1) <> kolor Then Fill x, y + 1, kolor
11.     If Point(x, y - 1) <> kolor Then Fill x, y - 1, kolor
12. End Sub

Give it a center point.  It then paints the pixels around it, if they're not already the proper color.  Then it moves to those pixels and repeats the process.  On and on, until the region to be painted is filled in completely.

Note, this should probably have a simple IF x < 0 or y < 0 or X >= _WIDTH or y >=_HEIGHT Then EXIT SUB in it just to make certain that it doesn't try to work itself to death off-screen on us.  ;)

[Dimster]

@bplus and @luke  ... Trapping I guess would be error code 256, which is too many gosub calls. So to monitor it I would think I need to count the number of calls to the routine and capture that number. If the routine does not error out I'm golden, but if it does then somehow I need to put a limit on the recursions being performed using that call count. In theory then, I should be able to identify the upper recursion limit of any of my recursive sub/function routines. Correct, or would the stack have other factors which would make the call count unreliable?


@SMcNeill ... is the variable "kolor" always = 0? If not how is the value for "kolor" assigned.   I'm thinking, if the kolor value is being calculated multiple times somewhere in your code, then that multiple call is the recursive stack loading problem that I missed seeing.

 Or does the subroutine itself would fall within the scope of "Recursive" because there are multiple "if" statements? I would think multiple 'if" statements would be quite a bit less of a stack load (ie the stack doesn't have to remember as many addresses).

[SMcNeill]

@bplus and @luke  ... Trapping I guess would be error code 256, which is too many gosub calls. So to monitor it I would think I need to count the number of calls to the routine and capture that number. If the routine does not error out I'm golden, but if it does then somehow I need to put a limit on the recursions being performed using that call count. In theory then, I should be able to identify the upper recursion limit of any of my recursive sub/function routines. Correct, or would the stack have other factors which would make the call count unreliable?


@SMcNeill ... is the variable "kolor" always = 0? If not how is the value for "kolor" assigned.   I'm thinking, if the kolor value is being calculated multiple times somewhere in your code, then that multiple call is the recursive stack loading problem that I missed seeing.

 Or does the subroutine itself would fall within the scope of "Recursive" because there are multiple "if" statements? I would think multiple 'if" statements would be quite a bit less of a stack load (ie the stack doesn't have to remember as many addresses).

For the Fill routine, you pass it the initial color ro fill when you call the SUB and then it simply repeats the call with that same color over and over.  In the example above, the fill color is &HFFFF0000 (or _RGBA32(255, 0, 0, 255) or solid Red).   We set the fill color on line 4 with the third parameter and the routine sticks with it to completion.

I simplified the process a bit; see if it's easier to understand now.  ;D


@@@@@@
@@@@@@
@@@@@@
@@@@@@
@@@@@@
@@@@@@

Let's pretend the above is my screen and that's all black...  Now, I draw a red box on it...

RRRRRR
R@@@@R
R@@@@R
R@@@@R
R@@@@R
RRRRRR

Now, choose a point inside that Red box (let's choose point 3,3) and color it Red.

RRRRRR
R@@@@R
R@R@@R
R@@@@R
R@@@@R
RRRRRR

Now, here's where the recursion comes in:
If the points above, left, right, below that point aren't Red, repeat the process for them <-- and recursively repeat this step as many times as is needed.

FIRST RECURSION:

RRRRRR
R@R@@R
RRRR@R
R@R@@R
R@@@@R
RRRRRR

See how we filled outwards?  Repeat that fill for our next positions...

SECOND RECURSION:

RRRRRR
RRRR@R
RRRRRR
RRRR@R
R@R@@R
RRRRRR


And so on, until we're done.  ;)

[luke]

I don't believe stack overflow can be effectively trapped (note the GoSub system is independent). On my system I just get a segmentation fault, Windows will probably have a similarly-fatal error.

It's also important to note that the stack size can differ between computers, so what works for you might not work elsewhere.

Still, let's assume a 1MB stack (not unreasonable). There's a bit of space taken at the start for bookkeeping and runtime stuff. A subroutine call takes 8 bytes for the return address, 8 bytes for bookkeeping and then space for local variables. If we have none, that's 16 bytes per stack frame which gives up a maximum call depth of about 65 thousand (actually 2^16). I haven't tested this, and I might have missed some extra local variables that are implicitly created by QB64, but hopefully it gives you an idea of the kind of scales to expect.

[SMcNeill]

I don't believe stack overflow can be effectively trapped (note the GoSub system is independent). On my system I just get a segmentation fault, Windows will probably have a similarly-fatal error.

It's also important to note that the stack size can differ between computers, so what works for you might not work elsewhere.

Still, let's assume a 1MB stack (not unreasonable). There's a bit of space taken at the start for bookkeeping and runtime stuff. A subroutine call takes 8 bytes for the return address, 8 bytes for bookkeeping and then space for local variables. If we have none, that's 16 bytes per stack frame which gives up a maximum call depth of about 65 thousand (actually 2^16). I haven't tested this, and I might have missed some extra local variables that are implicitly created by QB64, but hopefully it gives you an idea of the kind of scales to expect.

Windows just crashes the program with no warning.  We don't even get a nice segment fault.

As a note, I've seen recursive paint fills die many times before.  1980x1024 = 2+ million pixels...  If you end up recursively calling to them all, you'll definitely run out of stack space.

[Dimster]

Thanks guys.

[bplus]

If you want the easiest example of recursion, then I'd like to add in a simple Fill routine for folks to study:

Code: QB64: [Select]

1. Screen _NewImage(640, 480, 32)
2.  
3. Circle (240, 240), 200, &HFFFF0000
4. Fill 240, 240, &HFFFF0000
5.  
6. Sub Fill (x, y, kolor As _Unsigned Long)
7.     If Point(x, y) <> kolor Then Pset (x, y), kolor
8.     If Point(x + 1, y) <> kolor Then Fill x + 1, y, kolor
9.     If Point(x - 1, y) <> kolor Then Fill x - 1, y, kolor
10.     If Point(x, y + 1) <> kolor Then Fill x, y + 1, kolor
11.     If Point(x, y - 1) <> kolor Then Fill x, y - 1, kolor
12. End Sub

Give it a center point.  It then paints the pixels around it, if they're not already the proper color.  Then it moves to those pixels and repeats the process.  On and on, until the region to be painted is filled in completely.

Note, this should probably have a simple IF x < 0 or y < 0 or X >= _WIDTH or y >=_HEIGHT Then EXIT SUB in it just to make certain that it doesn't try to work itself to death off-screen on us.  ;)

Weird I can't get this sucker to work?? Not so simple. I got it working for x but when I uncomment next block with y, program dies.

Code: QB64: [Select]

1. Screen _NewImage(640, 480, 32)
2.  
3. Circle (240, 240), 200, &HFFFF0000
4. Fill 240, 240, &HFFFF0000
5.  
6. Sub Fill (x, y, kolor As _Unsigned Long)
7.     _Source 0
8.     If Point(x, y) <> kolor Then
9.         PSet (x, y), kolor
10.         If x + 1 < _Width Then
11.             If Point(x + 1, y) <> kolor Then Fill x + 1, y, kolor
12.         End If
13.  
14.         If x - 1 >= 0 Then
15.             If Point(x - 1, y) <> kolor Then Fill x - 1, y, kolor
16.         End If
17.  
18.         ' next does not work???
19.         'If y + 1 < _Height Then
20.         '    If Point(x, y + 1) <> kolor Then Fill x, y + 1, kolor
21.         'End If
22.  
23.         'If y - 1 >= 0 And Point(y - 1, y) <> kolor Then Fill x, y - 1, kolor
24.     End If
25. End Sub
26.  

Well everything works on a way, way, way smaller radius?

Code: QB64: [Select]

1. Screen _NewImage(640, 480, 32)
2. _Delay .55
3. _ScreenMove _Middle
4. Circle (240, 240), 70, &HFFFF0000
5. Fill 240, 240, &HFFFF0000
6.  
7. Sub Fill (x, y, kolor As _Unsigned Long)
8.     If Point(x, y) <> kolor Then
9.         PSet (x, y), kolor
10.         If x + 1 < _Width Then
11.             If Point(x + 1, y) <> kolor Then Fill x + 1, y, kolor
12.         End If
13.  
14.         If y + 1 < _Height Then
15.             If Point(x, y + 1) <> kolor Then Fill x, y + 1, kolor
16.         End If
17.  
18.  
19.         If x - 1 >= 0 Then
20.             If Point(x - 1, y) <> kolor Then Fill x - 1, y, kolor
21.         End If
22.  
23.         If y - 1 >= 0 Then
24.             If Point(x, y - 1) <> kolor Then Fill x, y - 1, kolor
25.         End If
26.     End If
27. End Sub
28.  
29.  

I am kind of shocked. I have a Paint variation that works a heck of allot like this and I don't remember having troubles with it like I am with this. Maybe I am getting old and missing something?

[SMcNeill]

@bplus that's the stack space issue at play.  Too many recursive calls with the larger radius in action.

[bplus]

OK I checked back and I was not using recursion, whew!

[TempodiBasic]

Recursive method is not a must, it is only a method among the others possible to use to solve a ripetitive work.

Every recursive algorythm has its equivalent as Iterative algorythm and vice versa
https://en.wikipedia.org/wiki/Recursion_(computer_science)#Recursion_versus_iteration

so you can use recursive way if you usually do things in this way and you have a good resource machine as you can use iterative way if you usually do things in this way and you have a global view of the work to do.
I you are able to use both recursive both iterative, you have more ways to realize your task. :-)

[SMcNeill]

OK I checked back and I was not using recursion, whew!

You can cut down on the recursion a ton just by logically going in a straight line each pass, rather than filling in all 4 directions a point at a time.  I just chose the most inefficient way as an easy example of the recursive method of coding.

WHILE POINT (x + 1, y) <> RED
    PSET (x + 1, y), RED
    x = x + 1
    FillVertical (x + 1, y), RED
WEND

Let's say I'm painting to the right, like above.  My WHILE loop here will fill left to right so I don't need to check those points a second time.  All I need to check is the lines leading up or down off from those points....

I'd be filling via LINE rather than via points, which would be both faster and much less recursive in the end. 

[TempodiBasic]

as we can see it is  easy to go stack overflow

this a simple filling routine that uses PSET instruction used for all points of the rectangular to fill with a color
both in iterative mode both in recursive mode the module does only a PSET action at every call.

Copy, paste into our fantastic QB64 2.0.1 and press F5 to run....

Code: QB64: [Select]

1. ' fill a square : recursive way versus iterative way
2. ' TempoDiBasic 2021 11 01
3.  
4. Screen _NewImage(1200, 900, 32)
5.  
6. Dim Shared As Integer x1, x2, y1, y2
7. Dim Shared As Long Backcolor, Forecolor
8. Dim As Single t0, t1, t2
9. Backcolor = _RGBA32(255, 127, 39, 255)
10. Forecolor = _RGBA32(0, 125, 0, 255)
11. x1 = 100
12. x2 = 1100
13. y1 = 200
14. y2 = 700
15.  
16. Cls
17. Print "Itertive method..."
18. t0 = Timer
19. Cls , Backcolor
20. fill_iterative
21. t2 = Timer
22. t2 = t2 - t0
23. Print "Task iterative done in "; t2; " time"
24. Sleep 2
25.  
26. Cls
27. Print "recursive method..."
28. t0 = Timer
29. Cls , Backcolor
30. fill_recursive x1, y1
31. t1 = Timer
32. t1 = t1 - t0
33. Print "Task recursive done in "; t1; " time"
34. Sleep 2
35. Cls
36. Print "resuming...."
37. Print "Task recursive done in "; t1; " time"
38. Print "Task iterative done in "; t2; " time"
39. End
40.  
41. Sub fill_recursive (x, y)
42.     Static As Integer a, b
43.     'Dim As Integer a, b
44.     a = x
45.     b = y
46.     PSet (a, b), Forecolor
47.     If a <= x2 Then
48.         a = a + 1
49.     Else
50.         a = x1
51.         If b <= y2 Then b = b + 1 Else Exit Sub
52.     End If
53.     fill_recursive a, b
54. End Sub
55.  
56. Sub fill_iterative
57.     For i = x1 To x2
58.         For j = y1 To y2
59.             PSet (i, j), Forecolor
60.         Next
61.     Next
62. End Sub

you must have a stack overflow for recursion method also if it doesn't use other than an sum operation an IF and PSET...
the issue is not the STATIC value that you must preserve in recursion... also if you use a DIM as integer a,b you got the same stack overflow.
As Luke said the stack overflow comes out as a generic error catched by OS (Win10)
  [ You are not allowed to view this attachment ]  

[SMcNeill]

How you folks convince Windows to toss you an error message is beyond me.  All I get is a program close when it comes to a segment fault, with no notice at all that things went wrong.  :(

[bplus]

Yeah I get the run around circle and then we're back to IDE. Better than crashing though.