CODEWITHSUNDEEP
javascriptrecursioncallstack
Indiana Kernick
Indiana Kernick

Reputation: 5341

Avoiding call stack error

I know what call stack size exceeded means but I need a way around it.

I get it when I call this recursive function

function fill(x_y) {
    var locColor = getPx(x_y[0], x_y[1]);
    if (locColor != pref.color) {
        setPx(x_y[0], x_y[1], pref.color);
        if (getPx(x_y[0] - 1, x_y[1]) == locColor) {
            fill([x_y[0] - 1, x_y[1]]);
        }
        if (getPx(x_y[0], x_y[1] - 1) == locColor) {
            fill([x_y[0], x_y[1] - 1]);
        }
        if (getPx(x_y[0] + 1, x_y[1]) == locColor) {
            fill([x_y[0] + 1, x_y[1]]);
        }
        if (getPx(x_y[0], x_y[1] + 1) == locColor) {
            fill([x_y[0], x_y[1] + 1]);
        }
    }
}

It's for a canvas application.

x_y is simply x and y coordinates where fill was called.

setPx prints a rectangle on the canvas given coordinates.

getPx gets the color of a rectangle of the canvas given it's coordinates

pref.color is the color that the user has selected for setPx

Can this function be done without recursion?

Upvotes: 0

Views: 670

Answers (1)

dnozay
dnozay

Reputation: 24324

This fills in order:

  • left,
  • top,
  • right,
  • bottom

(unless I got the coordinates system wrong).

You can do a solution without recursion by using a list of x_y to process; and instead of using the stack for recursion, you use the list for storing the parameters for your next calls.

function fill(x_y) {
    var todo = [x_y];
    var iniColor = getPx(x_y[0], x_y[1]);
    while (todo.length) {
        var curr = todo[0];
        var locColor = getPx(curr[0], curr[1]);
        todo = todo.slice(1);
        if (locColor != iniColor) { continue; }
        if (locColor == pref.color) { continue; }
        setPx(curr[0], curr[1], pref.color);

        todo.push([curr[0]-1,curr[1]  ]);
        todo.push([curr[0],  curr[1]-1]);
        todo.push([curr[0]+1,curr[1]  ]);
        todo.push([curr[0],  curr[1]+1]);
    }
}

UPDATE: 2015-03-01

From the comments, this is not as good as the algorithm in the question because of the number of iterations. In this block, I didn't check the condition early, which means they are added to the todo list even though they may not be good candidates. And when the point is processed later, the condition is checked.

        todo.push([curr[0]-1,curr[1]  ]);
        todo.push([curr[0],  curr[1]-1]);
        todo.push([curr[0]+1,curr[1]  ]);
        todo.push([curr[0],  curr[1]+1]);

Solution: check early as in the question; before calling push.

Upvotes: 1

Related Questions