In computer graphics, there are many times we have to fill up an irregularly shaped region of the screen with a specified color. For example, in a paint program when you want to draw an object outline, and make it a solid color. The recursive flood fill algorithm can be used to solve this problem with very little code.

Consider the following code. Here we have a global 2D array of characters, and a recursive function called fill. In the main program we call fill with a starting position and print out the resulting array contents.

//---------------------------------------------- // Purpose: Demonstrate recursive flood fill // Author: John Gauch //---------------------------------------------- #include  using namespace std; const int ROWS = 5; const int COLS = 5; char pixel[ROWS][COLS]; //---------------------------------------------- void fill(int r, int c, char value) { // Check first terminating condition if ((r < 0) || (r >= ROWS) || (c < 0) || (c >= COLS)) return; // Check second terminating condition else if (pixel[r][c] == value) return; // Handle recursive case else { cout << r << " " << c << endl; pixel[r][c] = value; fill(r, c + 1, value); // ADD HERE } } //---------------------------------------------- void print() { for (int r = 0; r < ROWS; r++) { for (int c = 0; c < COLS; c++) if (pixel[r][c] != 0) cout << pixel[r][c]; else cout << '.'; cout << endl; } } //---------------------------------------------- int main() { fill(1, 1, '#'); print(); return 0; } 

Create a program with the code above, and compile and run it. The program should print the (r,c) coordinates as they are filled in with '#' characters, and then draw a picture of the final array.

Notice that the whole array was not filled in with '#' characters. This is because we are only filling in pixels in one direction in the array with the command "fill(r, c + 1, value)". Go back to the code, and add a second recursive function call in another compass direction (r+1,r-1,c+1,c-1) and see what happens. Does the revised program fill in the whole array with '#' characters?

Now go back in and reverse the order of the two recursive function calls in your code and see what happens. Does the program print the same output? Do you get a different picture? Cut and paste your program output below:

It turns out that there are four recursive cases we should consider if we plan to fill an irregularly shaped region, corresponding to the four compass directions (r+1,r-1,c+1,c-1). Go back to your program to add these four function calls, and run and test your code.

As you know, recursion can take up a lot of memory space on the stack when there are a lot of calls. Go back to the main program above, and change the value of ROWS and COLS to see if you can fill an array 100x100. What about 1000x1000?

It turns out that the operating system has put a limit on the size of the stack. This limit works fine for normal programs, but flood fill may exceed this limit for large images. The good news is that most operating systems provide a command to increase the default stack size.

If you are using the "bash" shell on Linux or MacOS, then you can look at the default limits with the command "ulimit -a". You should see a stack size limit of about 8192K. Now type the command "ulimit -s unlimited". This will allow us to use a LOT of stack space when running heavily recursive programs from the command line.

If you are using the "sh", "csh" or "tcsh" shell on Linux or MacOS, then you can look at the default limits by typing "limit". The stack size limit will probably be 8192K. You can increase this limit by typing "limit stacksize unlimited". This will allow you to run heavily recursive programs without stack overflows.

Cut and paste your final fill function below:

Recursive Flood Fill Algorithm

Completing and Testing Flood Fill

Parsing Recursive Grammars

One important application of recursion is in parsing strings to see if they are valid and performing any necessary calculations. Grammars are often used to formally specify what strings are allowed in a language. The way we do this is with "production rules".

Each production rule has a "non-terminal" on the left hand side that is normally named after the item we want to produce. For example, "Integer" or "Float" or "VariableName". On the right hand side of the arrow "->" we list the items that make up that non-terminal. If there are several ways to produce a non-terminal, we will have two or more production rules. Finally, the vertical line "|" stands for "or" and is used as a short hand notation instead of writing multiple production rules.

For example, the three production rules below indicate that an "Integer" is made up of one or more "Digits", and "Digits" can be any character between 0..9.

 Integer -> Digit Integer Integer -> Digit Digit -> [0|1|2|3|4|5|6|7|8|9] 

The first rule says that an integer can start with a digit and is followed by an integer. The second rule says that an integer could be a single digit, and the third rule defines a digit as one of ten possible characters.

The following recursive function is modeled on this grammar and extracts a string of digits from an input string. Notice that we have added error checking to avoid array bounds errors. More importantly, notice that we "look ahead" in the array for a non-digit to decide if it is time to terminate the recursion or make another recursive method call.

//---------------------------------------------- // Purpose: Demonstrate recursive grammars // Author: John Gauch //---------------------------------------------- #include  using namespace std; //---------------------------------------------- string ParseInt(const string Input, const int pos) { if ((pos < 0) || (pos >= Input.length())) return ""; else if ((Input[pos] < '0') || (Input[pos] > '9')) return ""; else return (Input[pos] + ParseInt(Input, pos+1)); } //---------------------------------------------- string ParseFloat(const string Input, const int pos) { // ADD HERE return ""; } //---------------------------------------------- int main() { string input = "123.456hello"; cout << "Input = " << input << endl; cout << "ParseInt = " << ParseInt(input, 0) << endl; cout << "ParseFloat = " << ParseFloat(input, 0) << endl; } 

Create a program with the code above, and run it several times with different input strings. Cut and paste your program output below:

Extending the Recursive Grammar

Since we have defined integers using a grammar, we can use this to define a typical floating point number as follows:

 Float -> Integer Float -> Integer '.' Integer 

Using this information, extend your program to include a new function called "ParseFloat" that recursively calls the ParseInt function to test input strings. For example, your function should return "123.456" for the sample input string above.

How should we do this? If you look at the grammar above, you will see that both Float rules start with Integer on the right hand side of the production rule. This means that the first thing we should do in the ParseFloat function is call the ParseInt function and save the result.

Then, we should look at the next character in the input string. If we see any character besides a '.', then we know the first grammar rule applies, and we should output the integer string we saved. If you see a '.' character, then we need to call ParseInt a second time and combine this with the first integer and a '.' to create the output string.

Implement your ParseFloat function using the logic described above, and test your program with several input strings. Cut and paste your modified program below:

Cut and paste your program output below: