Think of the recursion as a chain reaction. You change one pixel. That pixel tells its neighbors: "Hey, if you look like me, change yourself too!" They change and tell their neighbors. The process stops naturally when it hits a boundary (grid edge) or a pixel of a different color.
This is why flood fill works without an explicit visited array,the color change itself marks pixels as visited. Once a pixel is the new color, you will not recurse into it again.