Recursion

[Pete]

The QBasic keyword, FRE, was not included in QB64. FRE kept track of both memory and stack space.

FRE(-1) Reported the largest non-string array you could create.
FRE(-2) Reported unused stack space.
FRE(to the anything else) The unused free memory space for storing strings. I used to use FRE(0)

With advancements in memory and operating systems, I'd have to question if a FRE statement even could be adequately addressed in the present.

Pete

[Aurel]

I don't know where it is that old post in which we talk about
recursive descent parser in 3 functions ...
if this 3 functions work then RECURSION work properly.

this is the topic about recursion:
https://www.qb64.org/forum/index.php?topic=33.15

[Aurel]

also Steve code compile fine
but when i run it ..then crush ...
i asking why ??

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

i changed kolor var to _offset and then program started but then crush

[TempodiBasic]

@SMcNeill

hi Steve
I like this "convince"

How you folks convince Windows to toss you an error message is beyond me.

I run the code posted above using QB64 x64 2.0.1, the code is already evident. The OS is Windows 8.1Pro  on HP notebook  500HDD, 4 GB RAM,  Celeron 2.00Ghz CPU N2810.
(here compiling is a bit slower than other my notebooks)
The application windows disappears and Windows tosses that generic error message. And I presume that it is related to a stack overflow.
But as you said, Windows shows a generic error message and it is impossible to have back an error code.

@ very interesting FRE of QB45. I think that it is hard to have a similar function in Windows.

[TempodiBasic]

@Aurel
hi dear
the QB64 2.0 was born because developers have solved the recursive bug
see here how the old broken code works good now
  [ You are not allowed to view this attachment ]  

https://www.qb64.org/portal/changelog-for-v2-0/
https://www.qb64.org/forum/index.php?topic=4209.0

[SMcNeill]

also Steve code compile fine
but when i run it ..then crush ...
i asking why ??

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

i changed kolor var to _offset and then program started but then crush

The crash you're seeing is what happens if you try to do too much recursion -- you run out of stack space and crash.  Change the CIRCLE radius from 200 to something like 50 and then try it and the code will run fine. 

Different computers and different OSes have different amounts of stack space associated with them.  MODERN Windows defaults to only 1MB, while Linux is 8MB, if my memory is right, but older versions had lower limits and those values can be altered in different manners on different OSes and compilers... 

Which leads to a serious limit and issue with recursion -- how much is too much?  How many times can a routine call itself before crashing? 

That's hard to say.  Just because it works on YOUR system, it doesn't mean it will on somebody else's.  Limit recursive functions to small calls and be careful not to run out of the limited stack space you have.  As you're experiencing yourself, the crashes in Windows come with no warning and no diagnostic message.  Just POOF!!  Program closed!!

Everyone who codes always seems obsessed with the idea of recursive code, because of its simplicity (doesn't get much simpler than the fill routine above) -- but they also need to be aware of the serious limits which comes with such style coding. 

Honestly, in most cases, I'd personally try NOT to use recursion in my code, if I can avoid it.  However, there's times where its ease of implementation and limited use capacity aren't a big deal, and I'll toss it in something just to get it done and over with quickly.  In my mind, recursive routines go into the same category as BubbleSorts and GOTO statements -- generally best to avoid like the plague, but secretly used anyway in private when being lazy.

Just be aware of the limits when writing any type os sub/function/gosub that might end up calling itself repeatedly.

[Dimster]

In terms of the load on the stack: Lets say you have a program of a couple of thousand lines and in the main section there are multiple opening and closing files capturing tons of data and placing that in arrays. Then there are many many Do Loops with multiple If statements and Select Cases. Your program runs with no stack issues. Now suppose you can see where the lines of code can be reduced by eliminating the Do Loops with Recursive Subs or Functions. Would it be safe to conclude the effect of stack load is the same (ie there should be no issue)?

[SMcNeill]

In terms of the load on the stack: Lets say you have a program of a couple of thousand lines and in the main section there are multiple opening and closing files capturing tons of data and placing that in arrays. Then there are many many Do Loops with multiple If statements and Select Cases. Your program runs with no stack issues. Now suppose you can see where the lines of code can be reduced by eliminating the Do Loops with Recursive Subs or Functions. Would it be safe to conclude the effect of stack load is the same (ie there should be no issue)?

Not at all.  Your program is limited by OS memory.  On 32-bit systems that's around 1.5GB  of memory after system reserved stuff, and on 64-bit systems it's limited by your machine's physical memory.  Stack space is limited to ~ 1MB on Windows and ~ 8 MB on Linux.

That's an incredible reduction in total amount of memory available.  Recursion must always be used in decisive moderation.

[Dimster]

Would CLS clear the stack? If not, is there another command or routine which clears the stack. I would think the completion of the recursive sub or function clears the stack upon return to the main program for a fresh set of addresses but is that the only way the stack resets?

[Aurel]

heh yes
with 20 work!
even i am not sure that i understand it exactly how is connected with
circle radius( stupid me ..he he )..

[TempodiBasic]

@SMcNeill
I get crushing and this graphic output
with this code (note that radius is 30 and not 200)

Code: QB64: [Select]
  Screen _NewImage(640, 480, 32)
     
    Circle (240, 240), 30, &HFFFF0000
    Fill 240, 240, &HFFFF0000
     
    Sub Fill (x, y, kolor As  Long)
        If Point(x, y) <> kolor Then Pset (x, y), kolor
        If Point(x + 1, y) <> kolor Then Fill x + 1, y, kolor
        If Point(x - 1, y) <> kolor Then Fill x - 1, y, kolor
        If Point(x, y + 1) <> kolor Then Fill x, y + 1, kolor
        If Point(x, y - 1) <> kolor Then Fill x, y - 1, kolor
    End Sub

  [ You are not allowed to view this attachment ]  

I need to put

Code: QB64: [Select]

1. SLEEP 2

after SCREEN to be able to see window of program.

@Aurel
do you like to joke, surely you know that circle area = radius * radius * 3,14...........
have a fun with ricursion coding.

[bplus]

Would CLS clear the stack? If not, is there another command or routine which clears the stack. I would think the completion of the recursive sub or function clears the stack upon return to the main program for a fresh set of addresses but is that the only way the stack resets?

No CLS would not clear stack. Yes, just exiting the routine would clear the stack. I even tried that before we reached the 10,8xx number with that notorious Fill routine, almost worked. I managed to hack another cycle of Fill, as mentioned in the other thread.

[Dimster]

So we need a recursion call of the recursive sub/function .... I'm smiling, clearly this spells disaster. But, if you do not have a termination case for the recursion, and have it housed within a Do Loop which makes control calls to the recursive sub/function, then would the stack be cleared?

For Example
a=1000
b=a
c=a
Do
    Do
         Do
         CALL Recursive Sub/Function
          Loop Until a
    CALL Recursive Sub/Function
    Loop Until b
CALL Recursive Sub/Function
Loop Until c

As long as a,b or c have clear clean stacks at the beginning of their loops, then perhaps this method could handle larger numbers of address calls. Kinda combersome.

[bplus]

@Dimster

It just so happens I was thinking about this last night. A recursive routine can act as a loop.

Here is a quick Demo:

Code: QB64: [Select]

1. StartIndex = 2: stepperIndex = 2: DoneIndex = 20
2. For index = StartIndex To DoneIndex Step stepperIndex
3.     Print index ^ 2;
4. Next
5. Print
6. index = StartIndex
7. PrintSquare index, stepperIndex, DoneIndex
8.  
9. ' can be done recursively
10. Sub PrintSquare (index, stepper, indexDone)
11.     If index > indexDone Then Exit Sub
12.     Print index ^ 2;
13.     _Delay .1
14.     index = index + stepper
15.     PrintSquare index, stepper, indexDone
16. End Sub
17.  
18.  

Actually I had a little trouble with trying it this way:

Code: QB64: [Select]

1. StartIndex = 2: stepperIndex = 2: DoneIndex = 20
2. For index = StartIndex To DoneIndex Step stepperIndex
3.     Print index ^ 2;
4. Next
5. Print
6. index = StartIndex
7. PrintSquare index, stepperIndex, DoneIndex
8.  
9. ' can be done recursively
10. Sub PrintSquare (index, stepper, indexDone)
11.     If index > indexDone Then Exit Sub
12.     Print index ^ 2;
13.     PrintSquare index + stepper, stepper, indexDone
14. End Sub
15.  

Oh heck it works that way too. OK so it was before supper blood sugar low = good chance I spelled stepper wrong!

[Dimster]

Wow @bplus. I ran both versions with the termination case at 2,000,000 and they ran quickly with no hint of a stack over load issue. Thanks for this, I think these will be my templates. Very similar structure to Quick Sort.

The recursive sub I was working with had an input statement to grab a data item from a file and then I had a naked recursive call (ie no parameters). I had the termination case just before the naked call using the end of file. Looked to me that that should have worked but never could get it to run to the end of the file. Going to revamp using your routines as my template. Thanks again.