3

I have an image (an array of 1000 x 1000 pixels) of 1s and 0s. I was asked to do edge detection, so I wrote this program in C to traverse the figure. My idea was to convert every pixel surrounded by like pixels to white (1) and every pixel surrounded by at least one unlike pixel to black (0). And I used recursion.

This worked when the figure was small but I'm getting a "stack overflow" message with larger figures.

Is there some systematic technique to convert this to a "non-recursive" program - simulating recursion using a user defined stack?

Improve this question
11
  • possible duplicate of Can and do compilers convert recursive logic to equivalent non-recursive logic?
    – gnat
    Feb 18, 2015 at 16:43
  • 1
    @gnat Seems more likely to be a duplicate of programmers.stackexchange.com/questions/252591/…
    – Doval
    Feb 18, 2015 at 16:47
  • 1
    @gnat: Yes, but the question is not a duplicate. If you want to direct him to an answer that is relevant to his question, then by all means do so, but we don't close questions as duplicates of answers unless the question is a canonical one.
    – Robert Harvey
    Feb 18, 2015 at 16:49
  • 2
    @TVMohini the suggestion that gnat was looking at is that if you write your existing recursive algorithim in a way that is tail call optimizable, it won't take up any stack space. The other approach is the more generic "rewrite it with a while loop" which Doval's link provides. Without specifics not much more can be said than that. With specifics (the code), the question becomes one more suited to Stack Overflow. (And you might also want to look at What methods are there to avoid a stack overflow in a recursive algorithm?).
    – user40980
    Feb 18, 2015 at 16:54
  • 1
    Depending on your situation, a quick fix might be to increase your stack size. (For linux, see stackoverflow.com/questions/2279052/…) This might be useful if you don't need a general solution, just a quick fix for particular data.
    – Gort the Robot
    Feb 18, 2015 at 19:19

2 Answers 2

Reset to default
3

Read about call stack, tail calls, continuations, and continuation-passing style (CPS).

Then read about CPS conversion (or CPS transform). It a s systematic way to tranform a deep call stack into heap allocated structure and control.

There is no magic bullet here, CPS-conversion is just allocating the equivalent of call frames in the heap.

Read also Appel's book Compiling with Continuations and his old paper Garbage Collection can be Faster than Stack Allocation

In practical terms, you might be able to transform your naive C code by allocating most of the data in the heap.

Another way of thinking at that is to "invent" a specialized byte code (for your algorithm) and implement its stack based interpreter.

See also Gabriel Kerneis' Continuation Based C

The (Deutch-) Schorr Waite graph marking algorithm might also be inspirational.

Improve this answer
4

What you are doing is a variation on blob coloring or 8-way connectivity.

The traditional solution for this is recursive, and it can get into trouble with large blobs.

Years ago, a very brilliant young coworker came up with a way to do nonrecursive 8-way connectivity. It used two loops, one over the rows, one of the columns in each row, and a loop body that looked at the four "successor" pixels (East, Southeast, South, Southwest).

There was one catch and one minor gotcha.

The catch was that you had to maintain an auxiliary table of "equivalent colors", to handle the cases where two blobs that you thought were separate turned out to be connected. (Imagine a large letter X. Until you see the center of the X, you could be looking at a backslash and a slash.)

The minor gotcha was that the loop body had to be written in C macros, because subroutine call overhead was eating it alive.

This should give you something to think about.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.