Recursion: function stack limit is stifling

Hey guys,

This isnt really a bug, per se, but rather it seems to be a limitation of the compiler.

Here are two background threads pertaining to my problem:

http://www.blitzbasic.com/Community/posts.php?topic=61909

http://www.blitzbasic.com/Community/posts.php?topic=61962

I've developed a test program which you can compile in order to test this problem:

Graphics (800,600, 0)

'These variables control the size of the array, as well as dictate the depth of the recursive algorithms:
Global x_size:Int = 15
Global y_size:Int = 15

Global Container:Int[x_size,y_size]

'Comment out the first function call, traverseContainer() to get the program to run:
'____________________________________________________________________________________
traverseContainer(x_size/2, y_size/2)
'traverseSouthEast(x_size/2, y_size/2)
'traverseNorthWest(x_size/2, y_size/2)
'____________________________________________________________________________________

While Not AppTerminate()
	
	printContainer()
	
	GCCollect()
	Flip
	Cls
Wend 


'recursively goes through the container and changes all of the 0's to 1's:

Function traverseContainer(x_coord%, y_coord%)
		If Container[x_coord, y_coord] <> 1 Then 
			Container[x_coord, y_coord] = 1
		Else 
			Return 
		End If 
	
		If x_coord > 0 Then traverseContainer(x_coord - 1, y_coord)
		If x_coord < x_size - 2 Then traverseContainer(x_coord + 1, y_coord)
		If y_coord > 0 Then traverseContainer(x_coord, y_coord - 1)
		If y_coord < y_size - 2 Then traverseContainer(x_coord, y_coord + 1)

End Function 

'recursively traverses the container in the north and west directions only:

Function traverseNorthWest(x_coord%, y_coord%)
	If Container[x_coord, y_coord] <> 1 Then 
		Container[x_coord, y_coord] = 1
	Else  
		Return 
	End If 

	If x_coord > 0 Then traverseContainer(x_coord - 1, y_coord)
	If y_coord > 0 Then traverseContainer(x_coord, y_coord - 1)
	
End Function 

'recursively traverses the container in the south and east directions only:

Function traverseSouthEast(x_coord%, y_coord%)
	
	If Container[x_coord, y_coord] <> 1 Then 
		Container[x_coord, y_coord] = 1
	Else 
		Return 
	End If 
	

	If x_coord < x_size - 2 Then traverseContainer(x_coord + 1, y_coord)
	If y_coord < y_size - 2 Then traverseContainer(x_coord, y_coord + 1)

	
End Function 

'print the container to the screen:

Function printContainer()
	Local k:Int
	Local j:Int 
	
	For k=0 To x_size - 1
			For j=0 To y_size - 1
				DrawText Container[k,j], 225 + k * 30, 100 + j * 30
			Next
		Next 
End Function 

edit:

argh, nevermind, looks like I have to tweak my test case a bit more in order to get to the conditions which I found in my original program.

Actually, it seems that this is the magic number in this particular test case:

Global x_size:Int = 418
Global y_size:Int = 418

I'm having problems with this algorithm on a 12x16 array in my game program though :(

With 417 x 417 your example reaches a stack depth of 86739.

That should be enough for a 12 x 16 array.

Graphics 800 , 600 , 0

Global PendingCalls:Int = 0  ' calls to traverseContainer without a matching Return
Global MaxPending:Int = 0

Global x_size:Int = 417
Global y_size:Int = 417

Global Container:Int[x_size,y_size]

traverseContainer(x_size/2, y_size/2)

While Not AppTerminate()
	
	printContainer()
	
	GCCollect()
	Flip
	Cls
Wend 


Function traverseContainer(x_coord% , y_coord%)
	
	PendingCalls :+ 1
	maxPending = Max( PendingCalls, MaxPending )

		If Container[x_coord, y_coord] <> 1 Then 
			Container[x_coord, y_coord] = 1
		Else 
			PendingCalls :- 1
			Return 
		End If 
	
		If x_coord > 0 Then traverseContainer(x_coord - 1, y_coord)
		If x_coord < x_size - 2 Then traverseContainer(x_coord + 1, y_coord)
		If y_coord > 0 Then traverseContainer(x_coord, y_coord - 1)
		If y_coord < y_size - 2 Then traverseContainer(x_coord , y_coord + 1)
	
	PendingCalls :- 1
	Return

End Function 


Function printContainer()
	Local k:Int
	Local j:Int
	
	DrawText "x_size = " + x_size + "   y_size = " + y_size, 250 , 20

	DrawText "  Maximum stack depth = " + MaxPending, 250, 50	
	
	For k=0 To x_size - 1
			For j=0 To y_size - 1
				DrawText Container[k,j], 225 + k * 30, 100 + j * 30
			Next
		Next 
End Function 

Ok,

After further investigation, this does appear to be yer basic stack overflow.

You can rebuild bmk to extend the stack - change this line in bmk_util.bmx...

	cmd=CQuote(BlitzMaxPath()+"/bin/ld.exe")+" -s"

...to...

	cmd=CQuote(BlitzMaxPath()+"/bin/ld.exe")+" -s -stack 4194304"

...or use the stack size of your choice - the above will give you a 4M stack.

I think this is reserved stack mem, not commited - ie: it will only use memory if it has to, so you should be able to make it fairly large. Not sure, have to do a bit more research here as my previous assumptions appear to have been quite wrong!

In addition, debugger.stdio.bmx in appstub.mod does NOT handle recursive code well! Will be publishing a syncmods fix for this soon.

Could you make the stack size an option in bmk?

...accessible via the IDE, preferably. You took the words right out of my mouth, Mark Tiffany! Excellent idea.

Russell

Anyone needing such a big stack should seriously rethink their algorithm. Given bukky's approach no amount of stack space (or processor speed) is going to save that algorithm at higher resolutions.