How Many Recursive Calls Can Your System Take?

[George McGinn]

@bplus - Sorry, I confused Dav's post with yours. He's running a 32-bit OS.

@SMcNeill - I was confused by your comment about when a process will die. Yes, they all must "die" in some form or another, but as I understood your example, backing out of a call that was done recursively shouldn't die due to lack of memory for the stack, as you keep freeing up space when you go back. You will still have at least one entry in the stack per recursive call outstanding, which if you call SUB A twice and only back out of it once, then yes, eventually it will run out of space and die, but by backing out in the example here, it will run for twice as long.

Some of the same things were discussed in the other recursion post (https://www.qb64.org/forum/index.php?topic=4338.0).

Looking at the QSort program, SUBS QuickSort & QSort looks like it will eventually back out of the recursive calls, unlike the source code we are looking at here. That is probably why it runs to completion. We may be calling the sort subs 8 million times, but if I ran this in debug and checked the call stack, I bet that many of the recursive calls are indeed backed out. Bplus' code posted here stays in the FILL subroutine, and never goes back, which is why it abnormally terminates.

Yes, I'm Captain Obvious!!!!

EDIT: For anyone interested in learning more about the stack, a good place to start is: https://embeddedgurus.com/stack-overflow/2009/03/computing-your-stack-size/ and https://www.keil.com/appnotes/files/apnt_316.pdf

@George McGinn
I don't know where you got this idea, I just told you in this thread I am on 64 bit system.
You must have me confused with someone else.

[bplus]

Yes George and Steve, I can get 8,902,654 calls to Quicksort because I get fully extracted from one call and then call up another round with Quicksort.

I almost had that notorious Fill routine working by exiting the sub when recurrence reached 9000 about 1000 below the moment it dies. I saved the x, y at the time of exiting to restart the routine all over again at shared saveX, saveY. Outside after the call I check if saveX is not 0 and call the routine again Fill saveX, saveY, samecolor. That worked! so I put it into a loop:
Fill x, y, kolor
while saveX <> 0
    Fill saveX, saveY, kolor
wend
for some reason it quit after the 2nd cycle. Oh well, it was a hack anyway!

[bplus]

I'm getting 10,821 with Mark's code, also running 64 bit and windows. I can't get Steves "SUB foo : CALL foo : END SUB" to run at all. I did try to incorporate a print statement and a counting routine but all I got was a black screen and "press any key"

Other than the recursive feature of QSort, which seems never to crash for me, I think recursive subs and functions need more tools to help them (me) be less prone to crashes. Would QuickSort somehow be clearing the stack with each pass?  OR could it be the case that the Sorting Array has fixed addresses for each of the indexed values, so each call by the recursive subroutine is only accessing these fixed address? If the array has 100 indices then it's the same 100 addresses on the stack. Rather than 100 different address per sort ordering pass. (ie if it takes 20 passes to order the array then there would be 20 x 100 = 2000 address v's the fixed 100 address.

So I could get unlimited recursive calls as long as the addresses are fixed to a max of 10,821 rather than an ongoing creation of address on the stack?

@Dimster  don't take this 10,821 (which is so close to mine!) too seriously. I think the key to a successful recursive routine is
1. to check that an exit condition exists and to exit when that condition is reached.
2. the repetitive process makes a clear path to finishing by reaching that exit condition.

Steve's Fill routine is not a great example. No exit check and no clear path to finishing ie it continues to expand outward in 4 directions from every point.

[luke]

Just run the program with $console:only so you can see the output even after it crashes.

[SMcNeill]

Just run the program with $console:only so you can see the output even after it crashes.

With Windows, even the console disappears after a crash, leaving nothing behind.  Best way to get and keep a number is to just print it to disk each successful pass, like so:

Code: QB64: [Select]

1. Open "Recursive Count.txt" For Output As #1
2. Do
3.     count = count + 1
4.     Print count; "layers deep before crashing"
5.     Print #1, count; "layers deep before crashing"
6.     foo count
7. Loop
8.  
9. Sub foo (x)
10.     If x > 0 Then foo (x - 1)
11. End Sub

This goes in the stack one incremental step at a time, then backs back out freeing memory, until it reaches the point where it just can't go any further and then dies completely on you.

The last number my text file generates is 21669, so that's basically the max number of times I can call on the stack, when nothing else is making use of stack space as well (such as DLL addresses being stored in it or other such stuff...).

[johnno56]

Bplus.

64,957 Linux 64 bit each time...

[luke]

With Windows, even the console disappears after a crash, leaving nothing behind.  Best way to get and keep a number is to just print it to disk each successful pass, like so:

There was an implied ...and run it from an already-open console window.

[Aurel]

Steve's Fill routine is not a great example. No exit check and no clear path to finishing ie it continues to expand outward in 4 directions from every point.

Yes and each time function point(x,y) return value and that value accumulate his own amount on stack
or memory...i guess

[Cobalt]

my old antiquated machine runs to 16275, FYI