Author Topic: Recursion  (Read 13527 times)

0 Members and 1 Guest are viewing this topic.

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: Recursion
« Reply #15 on: November 01, 2021, 08:41:17 am »
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
Programming isn't difficult, only it's  consuming time and coffee

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Recursion
« Reply #16 on: November 01, 2021, 09:09:38 am »
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

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.  ;)
« Last Edit: November 01, 2021, 10:17:12 am by SMcNeill »
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline Dimster

  • Forum Resident
  • Posts: 500
    • View Profile
Re: Recursion
« Reply #17 on: November 01, 2021, 10:01:19 am »
@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).

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Recursion
« Reply #18 on: November 01, 2021, 10:13:16 am »
@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.  ;)
« Last Edit: November 01, 2021, 10:33:08 am by SMcNeill »
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline luke

  • Administrator
  • Seasoned Forum Regular
  • Posts: 324
    • View Profile
Re: Recursion
« Reply #19 on: November 01, 2021, 10:21:27 am »
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.

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Recursion
« Reply #20 on: November 01, 2021, 10:34:15 am »
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.
« Last Edit: November 01, 2021, 10:39:43 am by SMcNeill »
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline Dimster

  • Forum Resident
  • Posts: 500
    • View Profile
Re: Recursion
« Reply #21 on: November 01, 2021, 11:44:57 am »
Thanks guys.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Recursion
« Reply #22 on: November 01, 2021, 11:51:11 am »
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

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.  

Well everything works on a way, way, way smaller radius?
Code: QB64: [Select]
  1. Screen _NewImage(640, 480, 32)
  2. _Delay .55
  3. Circle (240, 240), 70, &HFFFF0000
  4. Fill 240, 240, &HFFFF0000
  5.  
  6. Sub Fill (x, y, kolor As _Unsigned Long)
  7.     If Point(x, y) <> kolor Then
  8.         PSet (x, y), kolor
  9.         If x + 1 < _Width Then
  10.             If Point(x + 1, y) <> kolor Then Fill x + 1, y, kolor
  11.         End If
  12.  
  13.         If y + 1 < _Height Then
  14.             If Point(x, y + 1) <> kolor Then Fill x, y + 1, kolor
  15.         End If
  16.  
  17.  
  18.         If x - 1 >= 0 Then
  19.             If Point(x - 1, y) <> kolor Then Fill x - 1, y, kolor
  20.         End If
  21.  
  22.         If y - 1 >= 0 Then
  23.             If Point(x, y - 1) <> kolor Then Fill x, y - 1, kolor
  24.         End If
  25.     End If
  26.  
  27.  

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?
« Last Edit: November 01, 2021, 12:08:57 pm by bplus »

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Recursion
« Reply #23 on: November 01, 2021, 12:09:28 pm »
@bplus that's the stack space issue at play.  Too many recursive calls with the larger radius in action.
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Recursion
« Reply #24 on: November 01, 2021, 12:14:10 pm »
OK I checked back and I was not using recursion, whew!

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: Recursion
« Reply #25 on: November 01, 2021, 12:48:03 pm »
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. :-)
Programming isn't difficult, only it's  consuming time and coffee

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Recursion
« Reply #26 on: November 01, 2021, 12:58:58 pm »
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. 
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: Recursion
« Reply #27 on: November 01, 2021, 01:51:11 pm »
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. Print "Itertive method..."
  17. t0 = Timer
  18. Cls , Backcolor
  19. fill_iterative
  20. t2 = Timer
  21. t2 = t2 - t0
  22. Print "Task iterative done in "; t2; " time"
  23.  
  24. Print "recursive method..."
  25. t0 = Timer
  26. Cls , Backcolor
  27. fill_recursive x1, y1
  28. t1 = Timer
  29. t1 = t1 - t0
  30. Print "Task recursive done in "; t1; " time"
  31. Print "resuming...."
  32. Print "Task recursive done in "; t1; " time"
  33. Print "Task iterative done in "; t2; " time"
  34.  
  35. Sub fill_recursive (x, y)
  36.     Static As Integer a, b
  37.     'Dim As Integer a, b
  38.     a = x
  39.     b = y
  40.     PSet (a, b), Forecolor
  41.     If a <= x2 Then
  42.         a = a + 1
  43.     Else
  44.         a = x1
  45.         If b <= y2 Then b = b + 1 Else Exit Sub
  46.     End If
  47.     fill_recursive a, b
  48.  
  49. Sub fill_iterative
  50.     For i = x1 To x2
  51.         For j = y1 To y2
  52.             PSet (i, j), Forecolor
  53.         Next
  54.     Next
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 ]  

Programming isn't difficult, only it's  consuming time and coffee

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Recursion
« Reply #28 on: November 01, 2021, 02:30:42 pm »
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.  :(
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Recursion
« Reply #29 on: November 01, 2021, 02:39:24 pm »
Yeah I get the run around circle and then we're back to IDE. Better than crashing though.