StackOverflowException when using recursive sub call

hung

Member
Licensed User
This does not happen in desktop but in ppc. I got overflow problem when the recursive call is big. Not sure how to resolve it.

Here is a portion of the code:

B4X:
Sub clearme(h, v, col, dr)
If h < 0 OR h > board.h - 1 Then Return
If v < 0 OR v > board.v - 1 Then Return
If blk(h, v).col = 0 Then Return
If blk(h, v).col = col Then
   blk(h, v).col = 0
   blk(h, v).upd = 1
   gRate = gRate + 1

   clearme(h - 1, v, col, 0)
   clearme(h, v - 1, col, 0)
   clearme(h + 1, v, col, 0)
   clearme(h, v + 1, col, 0)
end if
end sub
 

agraham

Expert
Licensed User
As parameters are passed on the stack you could try reducing the parameters to clearme to just h and v. Hold col in a global variable and abandon dr as it is doing nothing but wasting stack space. This will save a LOT of stack space as B4PPC numerics are 64 bits internally.
 

hung

Member
Licensed User
Thanks. I change the problem as on your advie.

B4X:
Sub cleanme(hv)
h = Int(hv / 100)
v = hv Mod 100

If h < 0 OR h > board.h - 1 Then Return
If v < 0 OR v > board.v - 1 Then Return
If blk(h, v).col = 0 Then Return
If blk(h, v).col = colpicked Then
   ' draw black before take out
   blk(h, v).col = 5
   blk(h, v).upd = 1
             form1.line(h * board.bw, v * board.bh, (h+1) * board.bw, (v+1) * board.bh, cBlack, BF)

   blk(h, v).col = 0
   blk(h, v).upd = 1
   
   gRate = gRate + 1

   cleanme((h - 1) * 100 + v)
   cleanme(h * 100 + v - 1)
   cleanme((h + 1)* 100 + v)
   cleanme(h * 100 + v + 1)
   
End If
End Sub
That helps a bit. But still got problem for 8x8 cells.:sign0188:
 

agraham

Expert
Licensed User
The problem now is that you are declaring local values for h and v. They are also located on the stack so you are effectively having 3 variables allocated on the stack for each call. Try passing h and v separately as in your original code. This saves a stack allocation per call (and avoids all that arithmetic in the function).
 

agraham

Expert
Licensed User
Actually your idea of passing just a single parameter was quite good. If my suggestion above fails then make h and v globals and keep the messy arithmetic. This should only put a single variable on the stack per call so you can go at least 3 times deeper than you could originally with four arguments on the stack. You will have to re-calculate h and v from hv between recursive calls as this is the only information saved between calls. It's messy and slow but may at least let you do what you want and you can't get any better than passing a single argument to a recursive call.



B4X:
Sub Globals
    Dim h,v
End Sub

Sub Set_h_and_v(hv)
    h = Int(hv / 100)
    v = hv Mod 100
End Sub

Sub MainProg
    .....
    ' preset h and v before call
    h=something
    v=somethingelse
    clearme(h*100+v)
    ....
End Sub

Sub cleanme(hv)
    If h < 0 OR h > board.h - 1 Then Return
    If v < 0 OR v > board.v - 1 Then Return
    If blk(h, v).col = 0 Then Return
    If blk(h, v).col = colpicked Then
        ' draw black before take out
        blk(h, v).col = 5
        blk(h, v).upd = 1
        form1.line(h * board.bw, v * board.bh, (h+1) * board.bw, (v+1) * board.bh, cBlack, BF)
        blk(h, v).col = 0
        blk(h, v).upd = 1   
        gRate = gRate + 1

        ' existing h and v are ok
        h=h-1 
        cleanme(h * 100 + v)

        ' don't know state of h and so reset them
        Set_h_and_v(hv)
        v = v-1
        cleanme(h * 100 + v)

        Set_h_and_v(hv)
        h=h+1
        cleanme(h * 100 + v)

        Set_h_and_v(hv)
        v = v+1
        cleanme(h * 100 + v )
   
    End If
End Sub
Disclaimer: Normally I try a bit of code before I post it but in this case I haven't so there may be a "gotcha" lurking in it that I haven't noticed.

EDIT: There was one but I've edited it out!
 
Last edited:

hung

Member
Licensed User
no other sub call in the clearme. there was one but i replace with the form1.line.
the board is 8x8=64 but full recuring may be big as 8x8 x 4 x n=256 x n calls.
what i thought is, the stack should be released when return from the cleanme (as atbeginning of the sub), then concurrant use of stack may as small as 8x8=64.
in fact the above loop is common for maze game solving.

i got no solution yet but to try non-recursive which is much complicate and slow.
 
Top