Why is the recursive function throwing a stack overflow exception?

Question

I'm implementing a fill holes algorithm, the value of byte 0 is used as the background because I need to implement a floodfill algorihtm first.
My code is giving me a Stack Overflow Exception if I use the check8 for the position of TopLeft, Left or BotLeft of my current pixel.
But its fine if I just use the Top, TopRight, Right, BotRight and Bot.
I checked using the instruments-allocation tool and yes I was getting a lot of malloc calls. But I don't know why it is behaving like that.

let FillHoles (img : Bitmap) =
    let bd = img.LockBits(Rectangle(0,0,img.Width,img.Height),ImageLockMode.ReadWrite,PixelFormat.Format32bppArgb)
    let mutable (p:nativeptr<byte>) = NativePtr.ofNativeInt (bd.Scan0)

    let rec check8 (point:nativeptr<byte>) x y =
        try 
            if (x>=0 && x<=img.Width-1 && y>=0 && y<=img.Height-1)then
                if((NativePtr.get point 0)=(byte 0)) then
                    NativePtr.set point 0 (byte 255)
//                  if (x<>0) then
//                      check8 (NativePtr.add point -4) (x-1) y //Left -4
//                  if (x<>0 && y<>0) then
//                      check8 (NativePtr.add point -(bd.Stride + 4)) (x-1) (y-1) //TopLeft
                    if (y<>0) then
                        check8 (NativePtr.add point -(bd.Stride)) x (y-1) //Top
                    if (x<>img.Width-1 && y<>0) then
                        check8 (NativePtr.add point -(bd.Stride - 4)) (x+1) (y-1)  //TopRight
                    if (x<img.Width-1) then
                        check8 (NativePtr.add point 4) (x+1) y //Right
                    if (x<>img.Width-1 && y<>img.Height-1) then
                        check8 (NativePtr.add point (bd.Stride + 4)) (x+1) (y+1) //BotRight
                    if (y<>img.Height-1) then
                        check8 (NativePtr.add point (bd.Stride)) x (y+1) //Bot
//                    if (x<>0 && y<>img.Height-1) then
//                        check8 (NativePtr.add point (bd.Stride - 4)) (x-1) (y+1) //BotLeft
        with
            | :? System.NullReferenceException as ex -> (printfn "%A" ex.Message)
            | :? System.StackOverflowException as ex -> (printfn "%A" ex.Message)

    for row in 0 .. img.Height-1 do
        for col in 0 .. img.Width-1 do
            if (row=0 || row=img.Height-1 || col=0 || col=img.Width-1) then
                check8 p row col
            p <- NativePtr.add p 4
        done
    done
    img.UnlockBits(bd)
    img

Generally in recursive functions, stack overflow exceptions occur when you do not have a proper exit condition. It causes your recursive function to get called infinitely until you run out of stack memory. http://en.wikipedia.org/wiki/Stack_overflow — Niroshan, Nov 11 '14 at 01:34
I suspect that you are going over the same areas twice. You need to bail out of the function if you have already checked a point - for example left->right->left->right etc will create an infinite loop — John Palmer, Nov 11 '14 at 03:06
@Niroshan I think you are right, checking tail recursion and this post right now http://stackoverflow.com/questions/1797241/while-or-tail-recursion-in-f-what-to-use-when — EinsL, Nov 11 '14 at 03:15
@JohnPalmer I believe the conditional (NativePtr.get point 0)=(byte 0)) is checking that. I will try to change this to a tail recursive and will try a more functional approach. — EinsL, Nov 11 '14 at 03:16
@EinSL I do not know much about f#. You can print something after each `if..then` and see which one is never finishing. Secondly, if your exit condition is `(NativePtr.get point 0)=(byte 0)` double check the set statement just after that. — Niroshan, Nov 11 '14 at 03:44
As it would take too much time (for me) to check your recursion limiting expressions (how deep recursion is) I can say for sure this is NOT tail recursive function as after "if (y<>0) then check8 ..." it needs to return to the caller to do "if (x<>img.Width-1 && y<>0) then check8 ...". Not tail recursion at all. — Milosz Krajewski, Nov 11 '14 at 13:11
I know my code above is not tail recursive I don't how to make it that way yet, right now I am using a stack and It is working fine, I will try again when I have some time. — EinsL, Nov 11 '14 at 19:50

Daniel · Accepted Answer · 2014-11-11T19:01:31.853

2

A tail call cannot occur in a try-catch. See How are tail calls compiled? in this blog post by the F# Team.

edited Nov 11 '14 at 19:01

answered Nov 11 '14 at 15:14

Daniel

47,404
11
101
179

score 0 · Answer 2 · answered Nov 11 '14 at 10:19

I was trying to do a tail recursive flood fill but I ran out of time so I implemented it with a stack.
The recursive one I couldn't debug it properly, my IDE was behaving strangely all the stack frames probably were messing with it.
There is probably a more functional approach.

let FloodFill (img : Bitmap) =
    let bd = img.LockBits(Rectangle(0,0,img.Width,img.Height),ImageLockMode.ReadWrite,PixelFormat.Format32bppArgb)

    let check4 x y =
        let (checkPointer:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*y+x*4)
        if(NativePtr.get checkPointer 0 = byte 0) then
            let st = Stack()
            st.Push(x,y)
            while(st.Count > 0) do
                let current = st.Pop()
                let xx = fst current
                let yy = snd current
                let (pointer:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*yy+xx*4)
                NativePtr.set pointer 0 (byte 255)

                if(xx+1<=img.Width-1)then
                    let (point:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*yy+(xx+1)*4)
                    if(NativePtr.get point 0 = byte 0) then
                        st.Push(xx+1,yy)
                if(xx-1>=0)then
                    let (point:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*yy+(xx-1)*4)
                    if(NativePtr.get point 0 = byte 0) then
                        st.Push(xx-1,yy)
                if(yy+1<=img.Height-1)then
                    let (point:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*(yy+1)+xx*4)
                    if(NativePtr.get point 0 = byte 0) then
                        st.Push(xx,yy+1)
                if(yy-1>=0)then
                    let (point:nativeptr<byte>) = NativePtr.add (NativePtr.ofNativeInt (bd.Scan0)) (bd.Stride*(yy-1)+xx*4)
                    if(NativePtr.get point 0 = byte 0) then
                        st.Push(xx,yy-1)

    for row in 0 .. img.Height-1 do
        for col in 0 .. img.Width-1 do
            if (row=0 || row=img.Height-1 || col=0 || col=img.Width-1) then
                check4 row col
        done
    done
    img.UnlockBits(bd)
    img

Why is the recursive function throwing a stack overflow exception?

2 Answers2