How about using a stack/queue to manage the remaining work?
public void Fill(int[,] array, int x, int y, int newInt)
{
int initial = array[x,y];
Queue<Tuple<int,int>> queue = new Queue<Tuple<int,int>>();
queue.Push(new Tuple<int, int>(x, y));
while (queue.Any())
{
Tuple<int, int> point = queue.Dequeue();
if (array[point.Value1, point.Value2] != initial)
continue;
array[point.Value1, point.Value2] = newInt;
EnqueueIfMatches(array, queue, point.Value1 - 1, point.Value2, initial);
EnqueueIfMatches(array, queue, point.Value1 + 1, point.Value2, initial);
EnqueueIfMatches(array, queue, point.Value1, point.Value2 - 1, initial);
EnqueueIfMatches(array, queue, point.Value1, point.Value2 + 1, initial);
}
}
private void EnqueueIfMatches(int[,] array, Queue<Tuple<int, int>> queue, int x, int y, int initial)
{
if (x < 0 || x >= array.GetLength(0) || y < 0 || y >= array.GetLength(1))
return;
if (array[x, y] == initial)
queue.Enqueue(new Tuple<int, int>(x, y));
}