StackOverflowException when using recursive sub call

Discussion in 'Questions (Windows Mobile)' started by hung, Aug 30, 2007.

  1. hung

    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:

    Code:
    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
     
  2. agraham

    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.
     
  3. hung

    hung Member Licensed User

    Thanks. I change the problem as on your advie.

    Code:
    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:
     
  4. agraham

    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).
     
  5. agraham

    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.



    Code:
    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: Aug 31, 2007
  6. agraham

    agraham Expert Licensed User

    I am surprised that what looks like a maximum recursion depth of 64 is running out of stack space! Are you doing something else that eats stack space like calling a recursive call within a recursive call?
     
  7. hung

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