How Many Recursive Calls Can Your System Take?

[bplus]

Find out here!

Code: QB64: [Select]

1. _Title "About How Many Recursive Calls Can Your Systen Take?" ' b+ 2021-11-02
2. Screen _NewImage(800, 600, 32)
3. Dim Shared recurrance
4. Print "Pausing a second at every 1000."
5. Line (150, 100)-Step(501, 401), &HFFFFFF00, B
6. Fill 151, 101, &HFFFFFF00
7.  
8. Sub Fill (x, y, kolor As _Unsigned Long)
9.     recurrance = recurrance + 1
10.     Locate 3, 1: Print Space$(10)
11.     Locate 3, 1: Print recurrance
12.     If recurrance Mod 1000 = 0 Then _Delay 1 Else _Delay .01
13.     If Point(x, y) <> kolor Then PSet (x, y), kolor
14.     If Point(x + 1, y) <> kolor Then Fill x + 1, y, kolor
15.     If Point(x - 1, y) <> kolor Then Fill x - 1, y, kolor
16.     If Point(x, y + 1) <> kolor Then Fill x, y + 1, kolor
17.     If Point(x, y - 1) <> kolor Then Fill x, y - 1, kolor
18. End Sub
19.  
20.  

Mine died at 1810.

No that was 18010 I think 2md time was 18009.

[George McGinn]

I ran this code on both my DELL Optiplex 990 running Ubuntu Linux and on my MACBook Pro 14.1 (2019 version) running OSX BigSur, and this is what I get:

MAC OSX - 2965 (That was close to the last number I saw before the console closed and the OSX Problem Report displayed0
LINUX -  >86,000 (When I got the error on my MAC, i looked at my Linux and it was in the 86,000 mark. As soon as I looked back from my MAC to the Linux, it had terminated).

@bplus - Were you running it on Windows? That would explain why Linux allows a greater number of recursion calls.

If not, I can provide you with my hardware specs, if you think that has anything to do with it.

[bplus]

Ok this works better, it documents the last recursive call count before dying!

Code: QB64: [Select]

1. _Title "About How Many Recursive Calls Can Your Systen Take?" ' b+ 2021-11-02
2. Screen _NewImage(800, 600, 32)
3. Dim Shared recurrance
4. Print "Pausing a second at every 1000."
5. Line (150, 100)-Step(501, 401), &HFFFFFF00, B
6. Fill 151, 101, &HFFFFFF00
7.  
8. Sub Fill (x, y, kolor As _Unsigned Long)
9.     recurrance = recurrance + 1
10.     Open "Recursive Count.txt" For Output As #1
11.     Print #1, recurrance
12.     Close #1
13.     Locate 3, 1: Print Space$(10)
14.     Locate 3, 1: Print recurrance
15.     If recurrance Mod 1000 = 0 Then _Delay 1
16.     If Point(x, y) <> kolor Then PSet (x, y), kolor
17.     If Point(x + 1, y) <> kolor Then Fill x + 1, y, kolor
18.     If Point(x - 1, y) <> kolor Then Fill x - 1, y, kolor
19.     If Point(x, y + 1) <> kolor Then Fill x, y + 1, kolor
20.     If Point(x, y - 1) <> kolor Then Fill x, y - 1, kolor
21. End Sub
22.  
23.  

So now I know the number is over 10,800. I had set a beep at 17,500 to wake me but never heard it. So might have misread first numbers.

BTW delays from the start seem to help the code stay in play instead of a quick death. So there might be a racing issue involved here too!

@George McGinn  yes Windows 10, 5 year old laptop.

[Dav]

Mine stopped right after the 16,000 mark.  Couldn't see the exact number because the screen whitened out.  I'm running Win7 32bit.

Edit:  I get 16,275.

- Dav

[bplus]

With 2nd code I am getting 10,824, 3 times in row.

[George McGinn]

I wasn't sure about the 80,000 plus number, so I ran it again, this time writing the recurrance value to a file.

I get 65,478 on my Linux machine (I ran the test 3 times and got the same number).

I ran the same test on my MAC 3 times, and I get 3,262.

I feared I mis-read the number, as it was flying by so fast on the display.
 

[bplus]

Checking for racing conditions I made some mods adding more delays for screen to set and a tiny delay back in at each print of count (along with printing count to file).

Code: QB64: [Select]

1. _Title "About How Many Recursive Calls Can Your Systen Take?" ' b+ 2021-11-02
2. Screen _NewImage(800, 600, 32)
3. _Delay .25
4. _ScreenMove _Middle
5.  
6. Dim Shared recurrance
7. Print "Pausing a second at every 1000."
8. Line (150, 100)-Step(501, 401), &HFFFFFF00, B
9. Fill 151, 101, &HFFFFFF00
10.  
11. Sub Fill (x, y, kolor As _Unsigned Long)
12.     recurrance = recurrance + 1
13.     Open "About How Many Recursive Count.txt" For Output As #1
14.     Print #1, recurrance
15.     Close #1
16.     Locate 3, 1: Print Space$(10)
17.     Locate 3, 1: Print recurrance
18.     If recurrance Mod 1000 = 0 Then _Delay 1 Else _Delay .001
19.     If Point(x, y) <> kolor Then PSet (x, y), kolor
20.     If Point(x + 1, y) <> kolor Then Fill x + 1, y, kolor
21.     If Point(x - 1, y) <> kolor Then Fill x - 1, y, kolor
22.     If Point(x, y + 1) <> kolor Then Fill x, y + 1, kolor
23.     If Point(x, y - 1) <> kolor Then Fill x, y - 1, kolor
24. End Sub
25.  
26.  

Also I turned off Browser to save resources (but still had on File Explorer to run program and Notepad++ to read count file. I am getting a very consistent 10824 in .txt file (changed name too so that it sits right under the .bas and .exe for finding quickly in file explorer.

[bplus]

Hmm... I guess it depends on the code that you use a recursive sub in. In QSort I call it 8,902,654 times and the program doesn't die:

Code: QB64: [Select]

1. _Title "Recursive Vrs NonRecursive #2 test with Quicksort" 'b+ 2021-11-01
2. '2021-11-01 #2 test try a recursive sub wo parameters
3.  
4. _Define A-Z As _UNSIGNED _INTEGER64
5. ReDim Shared As _Unsigned _Integer64 ArrayHigh, StackPt
6. ArrayHigh = 10000000
7. ReDim Shared n(1 To ArrayHigh), m(1 To ArrayHigh), o(1 To ArrayHigh)
8. ReDim Shared Stack(0 To ArrayHigh \ 8)
9. Dim Shared recurrence
10.  
11. For i = 1 To ArrayHigh
12.     n(i) = i
13. Next
14. For i = ArrayHigh To 2 Step -1 ' Fisher Yates Shuffle
15.     Swap n(i), n(Int(Rnd * i) + 1)
16.     m(i) = n(i) ' copy m off n
17.     o(i) = n(i)
18. Next
19. m(1) = n(1)
20. o(1) = n(1)
21. Print "Test arrays ready. Testing Recursive QuickSort first."
22.  
23. T# = Timer(.001)
24. QuickSort 1, ArrayHigh
25. QuickSortT# = Timer(.001) - T#
26. For i = 1 To ArrayHigh
27.     If n(i) <> i Then Beep: Print "Error in QuickSort array n."
28. Next
29. Print "QuickSort checked, QuickSort time was"; QuickSortT#
30.  
31. T# = Timer(.001)
32. Quicksort_QB64
33. QuicksortQB64T# = Timer(.001) - T#
34. For i = 1 To ArrayHigh
35.     If m(i) <> i Then Beep: Print "Error in Quicksort__QB64 array m."
36. Next
37. Print "Quicksort_QB64 checked, Quicksort_QB64 time was"; QuicksortQB64T#
38.  
39. T# = Timer(.001)
40. StackPt = StackPt + 1
41. Stack(StackPt) = 1
42. StackPt = StackPt + 1
43. Stack(StackPt) = ArrayHigh
44. QSort
45. QSortT# = Timer(.001) - T#
46. For i = 1 To ArrayHigh
47.     If o(i) <> i Then Beep: Print "Error in QSort array o."
48. Next
49. Print "QSort checked, QSort time was"; QSortT#
50. Print "Number of calls to QSort"; recurrence
51.  
52. ' recursive
53. Sub QuickSort (start As _Unsigned _Integer64, finish As _Unsigned _Integer64)
54.     Lo = start: Hi = finish
55.     Middle = n((Lo + Hi) \ 2)
56.     Do
57.         Do While n(Lo) < Middle: Lo = Lo + 1: Loop
58.         Do While n(Hi) > Middle: Hi = Hi - 1: Loop
59.         If Lo <= Hi Then
60.             Swap n(Lo), n(Hi)
61.             Lo = Lo + 1: Hi = Hi - 1
62.         End If
63.     Loop Until Lo > Hi
64.     If Hi > start Then QuickSort start, Hi
65.     If Lo < finish Then QuickSort Lo, finish
66. End Sub
67.  
68. ' non recursive
69. ' ref:  https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64
70. Sub Quicksort_QB64
71.     Left = LBound(m)
72.     Right = UBound(m)
73.     LeftMargin = Left
74.     ReDim Stack&&(Left To Right)
75.     StackPtr = 0
76.     StackPtr = StackPtr + 1
77.     Stack&&(StackPtr + LeftMargin) = Left
78.     StackPtr = StackPtr + 1
79.     Stack&&(StackPtr + LeftMargin) = Right
80.     Do 'Until StackPtr = 0
81.         Right = Stack&&(StackPtr + LeftMargin)
82.         StackPtr = StackPtr - 1
83.         Left = Stack&&(StackPtr + LeftMargin)
84.         StackPtr = StackPtr - 1
85.         Do 'Until Left >= Right
86.             Pivot~&& = m((Left + Right) \ 2)
87.             Indx = Left
88.             Jndx = Right
89.             Do
90.                 Do While (m(Indx) < Pivot~&&)
91.                     Indx = Indx + 1
92.                 Loop
93.                 Do While (m(Jndx) > Pivot~&&)
94.                     Jndx = Jndx - 1
95.                 Loop
96.                 If Indx <= Jndx Then
97.                     If Indx < Jndx Then Swap m(Indx), m(Jndx)
98.                     Indx = Indx + 1
99.                     Jndx = Jndx - 1
100.                 End If
101.             Loop While Indx <= Jndx
102.             If Indx < Right Then
103.                 StackPtr = StackPtr + 1
104.                 Stack&&(StackPtr + LeftMargin) = Indx
105.                 StackPtr = StackPtr + 1
106.                 Stack&&(StackPtr + LeftMargin) = Right
107.             End If
108.             Right = Jndx
109.         Loop Until Left >= Right
110.     Loop Until StackPtr = 0
111. End Sub
112.  
113. ' recursive No Parameters!!!
114. Sub QSort
115.     recurrence = recurrence + 1
116.     If StackPt > 0 Then 'else done!
117.         finish = Stack(StackPt) 'pull off last 2 arguments
118.         StackPt = StackPt - 1
119.         start = Stack(StackPt)
120.         StackPt = StackPt - 1
121.  
122.         Lo = start: Hi = finish
123.         Middle = o((Lo + Hi) \ 2)
124.         Do
125.             Do While o(Lo) < Middle: Lo = Lo + 1: Loop
126.             Do While o(Hi) > Middle: Hi = Hi - 1: Loop
127.             If Lo <= Hi Then
128.                 Swap o(Lo), o(Hi)
129.                 Lo = Lo + 1: Hi = Hi - 1
130.             End If
131.         Loop Until Lo > Hi
132.  
133.         If Hi > start Then
134.             StackPt = StackPt + 1
135.             Stack(StackPt) = start
136.             StackPt = StackPt + 1
137.             Stack(StackPt) = Hi
138.             QSort
139.         End If
140.         If Lo < finish Then
141.             StackPt = StackPt + 1
142.             Stack(StackPt) = Lo
143.             StackPt = StackPt + 1
144.             Stack(StackPt) = finish
145.             QSort
146.         End If
147.     End If
148. End Sub
149.  
150.  
151.  

[George McGinn]

@bplus I too ran your new code with everything shut down, except for terminal and htop on my Linux.

I get the same 65,478 number.

I also noticed just now you are running a 32-bit machine, where both of mine are 64-bit machines.

When I ran it from my Linux terminal, I get a message "Segmentation fault (core dumped)" error message, which does not show up when running from the IDE. I checked the run on my MAC OSX, and it gets a similar error message.

This is a memory error - more specifically, the program is trying to access memory that doesn't belong to it. I have 32GB of RAM on my Linux Optiplex computer, where my MACBook Pro only has 8GB of RAM. What is the RAM on your PC?

However, it seems that this memory is also affected by the OS/Kernel running, and yes, other processes. Unless you are actively running memory intensive processes, stopping applications will not have an effect on your results. What usually happens is that most all processes are swapped out when an active program is running, freeing up memory. Also, having SWAP memory available will effect your results. In Linux, I have vm.swappiness set to 60, which means it will grab memory from the SWAP file before RAM is exhausted.

Now having said that, on my Linux system, your program maxes out two of my four-core CPU's. Running a monitoring program, it seems that I get this error when one of my CPU's hits 103% utilization. However, my RAM usage never exceeds 5%. I also verified this using the htop utility as well. So while I get a Segmentation Fault error, I am wondering if this is also displayed when I exceed my CPU utilization? It should only be based on the amount of memory available to the program, or the memory the OS/Kernel allocates to it.

[bplus]

Hey @George McGinn actually I'm on a 64 bit system and processor also 8 GB Ram.

I am starting to suspect the problem is not number calls to recursive routine but the actual routine. Fill is using 4 parameters. I just tested the other call to recursive QuickSort that took 2 parameters. No difference compared to one using no parameters the time is longer because I used a pseudo stack instead of internal for the parameters.

[SMcNeill]

@bplus remember: It's not calls the routine makes to itself; it's calls that are made before completion.

SUB foo (x)
   IF x > 0 THEN foo (x -1)
END SUB

Now, if we pass foo 10, we'll recurse 10 layers deep and then back back out of them, with no issue.

FOR i = 1 to 10
   foo (10)
NEXT

A static counter, as you're using would give a value of 100 iwith the FOR loop, but we never went more than 10 layers deep.

I'd think a decent stack counter might be something more like:


DO
   count = count + 1
   PRINT count
   foo (count)
LOOP UNTIL CRASH

SUB foo (x)
   IF x > 0 THEN foo (x -1)
END SUB

Go in, one layer at a time, back out, and repeat to see how deep you go before dying.

[George McGinn]

@bplus - You said you were running a 32-bit Windows OS, which manages memory as if it were running on a 32-bit system. This is why you can't install a 64-bit system on a 32-bit machine, but you can install 32-bit software on a 64-bit PC. You will only get addressing out to 32 bits.

@SMcNeill - By calling and backing out of a recursive call, don't you free up memory in the stack? If you back out of a recursive call, you should be able to execute them forever, no? If you call a routine and back out of it, it would not be recursive? I thought that is what you said in the beginning of your post, but I'm confused why we would see how deep you go before dying. It shouldn't die.

I still think this is a memory issue, and the combo of the program running, the OS/Kernel, and hardware configuration that will dictate what and how many calls you can do by continually calling a recursive routine without backing out of any of the calls. This is why bplus' program shows a huge discrepancy between my Linux and MAC OSX systems running the same exact code from the same version of the QB64 IDE.

[bplus]

@bplus - You said you were running a 32-bit Windows OS, which manages memory as if it were running on a 32-bit system. This is why you can't install a 64-bit system on a 32-bit machine, but you can install 32-bit software on a 64-bit PC. You will only get addressing out to 32 bits.

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

[SMcNeill]

@SMcNeill - By calling and backing out of a recursive call, don't you free up memory in the stack? If you back out of a recursive call, you should be able to execute them forever, no? If you call a routine and back out of it, it would not be recursive? I thought that is what you said in the beginning of your post, but I'm confused why we would see how deep you go before dying. It shouldn't die.

If a routine calls itself, it's recursive. 

And you're right, backing out frees the resources on the stack, so as long as you backout before running out of stack space, your program can run forever.

As for "it shouldn't die", that type of thinking is wrong.  It *HAS* to die at some point.  Your program has to keep track of a return address every time you call a function.  Think about it for a moment.

CLS
PRINT "Hello World"
CALL foo
PRINT "Second Hello."

SUB foo
  PRINT "I'm in a sub..."
END SUB

With the above, program flow goes from CLS to PRINT to SUB foo to PRINT and then back to where we called foo...  That end sub stores a return address in memory so we can return back to the next line after calling it.

Now, if we had a sub like this:

SUB foo
   CALL foo
END SUB

We'd end up going deeper and deeper, and never reaching a return point.  We'd store an extra return address over and over and over,using ever more memory.

Without a limit on stack space, we'd eventually eat up ALL the memory on our PC until it became so unstable everything crashed...

And this, manufactures give us a limited amount of stack space so the worstwe can do is crash a single misbehaving program and not the whole PC.

[Dimster]

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?