CSCE 2014 - Laboratory Assignment 7

    The objective of this lab is to work more with recursive functions. In particular, we will see how recursion can be used to process 2D arrays in interesting ways, and to parse recursive grammars.

  1. Recursive Flood Fill Algorithm
  2. 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 <iostream>
    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. Go back to the code, and add a second recursive function call in the fill program 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 and see what happens. Does the program print the same output? Do you get a different picture? Cut and paste your program output below:

  3. Completing and Testing Flood Fill
  4. 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. 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:

  5. Parsing Recursive Grammars
  6. 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. For example, the three rules below indicate that an integer is made up of one or more digits 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 <iostream>
    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:

  7. Extending the Recursive Grammar
  8. 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. 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:

  9. Submit Work
  10. When you have completed all of the steps to this lab:

    Enter your FIRST name:
    Enter your LAST name:
    Enter your UAID number: