Home CPSC 220

Recursion Continued

Euclid's Algorithm

One of the oldest known algorithms is Euclid's Algorithm dating to 300 BC. The algorithm finds the greatest common divisor (GCD) of two numbers. The algorithm can be expressed recursively:

To find the greatest common divisor of $X$ and $Y$:

  1. If $Y$ is zero, the GCD is $X$.
  2. Else if $X \geq Y$, the GCD is the GCD of $Y$ and $(X \ mod\ Y)$
  3. Else the GCD is the GCD of $Y$ and $X$.

How can we implement this as a recursive function in Java?






Example: Efficient Power Computation

In Java, there is no operator for computing exponents (like Python's **). We can use the Math.pow function, or we can roll our own.

If we were to write a version of this, we could use this solution:

$2^8 = 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2$

$3^5 = 3 \times 3 \times 3 \times 3 \times 3$

We could instead use this more efficient solution:

$2^8 = 2^4 \times 2^4$

$3^5 = 3^2 \times 3^2 \times 3$

We can generalize this as:

\[ X^Y = \begin{cases} X^{(Y/2)} \times X^{(Y/2)} \hfill & \text{ if $Y$ is even} \\ X^{(Y/2)} \times X^{(Y/2)} \times X \hfill & \text{ if $Y$ is odd} \\ \end{cases} \]

What should the base case be?

How can we use this algorithm to write a Java version of the pow function?





How much more efficient is this recursive solution?


Flood Fill

"Flood fill" refers to doing a search and replace in a 2D area, where we only do the replace on areas that are "reachable" from the starting point, in an area of the same original value.

It is used by the "paint can" tool in graphics programs, and also in games like Minesweeper. This problem is best solved recursively. How can we develop a recursive algorithm to perform flood filling?





Below is a program which draws a randomly colored grid, and calls an empty floodFill function when the user clicks on a cell in the grid. How can we implement our algorithm in this program?


import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

// we only have a few colors in this
enum ColorCode {
    Red,
    Green,
    Blue,
    Black
}

// the gameworld is a component, so it can be added to a GUI program
class GameWorld extends JComponent implements MouseListener {
    // we make an array of colors for our component
    private ColorCode grid[][];
    private final int SIZE = 5;
    private final int N = 100;

    // set it up to be randomly colored
    public GameWorld() {
        grid = new ColorCode[N][N];

        Random generator = new Random();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // pick a random color from three options
                grid[i][j] = ColorCode.values()[generator.nextInt(3)];
            }
        }
    }

    @Override
    public void paintComponent(Graphics g) {
        // draw the grid as squares
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                switch (grid[i][j]) {
                    case Red:
                        g.setColor(Color.RED);
                        break;
                    case Green:
                        g.setColor(Color.GREEN);
                        break;
                    case Blue:
                        g.setColor(Color.BLUE);
                        break;
                    case Black:
                        g.setColor(Color.BLACK);
                }
                g.fillRect(i * SIZE, j * SIZE, SIZE, SIZE);
            }
        }
    }
    
    @Override
    public void mouseClicked(MouseEvent e) {
        // find which coordinates they clicked on
        int row = e.getX() / SIZE;
        int col = e.getY() / SIZE;
        
        // begin the flood fill process here
        floodFill(row, col, grid[row][col], ColorCode.Black);
        
        // redraw it
        revalidate();
        repaint();
    }

    // the ones we don't care about
    public void mousePressed(MouseEvent e) {}
    public void mouseReleased(MouseEvent e) {}
    public void mouseEntered(MouseEvent e) {}
    public void mouseExited(MouseEvent e) {}
    
    // the flood fill function
    public void floodFill(int row, int col, ColorCode source, ColorCode dest) {

        
        
        
        
        
        
    }
}

public class FloodFill {
    public static void main(String args[]) {
        JFrame frame = new JFrame("Flood Fill Example!");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        GameWorld g = new GameWorld();
        g.addMouseListener(g);
        frame.add(g);
        frame.setSize(530, 550);
        frame.setVisible(true);
    }
}

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.