NewsForumsCodeLogsGallerySpecsSearch

Recursion: function stack limit is stifling

BlitzMax Forums/BlitzMax Programming/Recursion: function stack limit is stifling

Bukky(Posted 2006) [#1]
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.


Bukky(Posted 2006) [#2]
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 :(


Floyd(Posted 2006) [#3]
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



marksibly(Posted 2006) [#4]
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.


Mark Tiffany(Posted 2006) [#5]
Could you make the stack size an option in bmk?


Russell(Posted 2006) [#6]
...accessible via the IDE, preferably. You took the words right out of my mouth, Mark Tiffany! Excellent idea.

Russell


skidracer(Posted 2006) [#7]
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.