Problems

Problem 1

Create a class called "RecursiveMethods" and write a recursive method called "printStars" that takes a nonnegative integer as a parameter and generates the following pattern of stars. If the nonnegative integer is 4, then the pattern generated is:

**** *** ** * * ** *** **** 

Note, there is a newline after the last row of stars. The method should be static. Here is how the method should be defined:

 public static void printStars(int n) { // TODO code goes here... }

Problem 2

Read the Raising a Number to Power in textbook pp. 303 304. Write a recursive static method in the "RecursiveMethods" class created in Problem 1 called "power" that takes a number and a power as integer parameters and calculate the power of the number. For example, if the number is 2 and power is 8, the method will calculate 2⁸ and return 256.

Here's how to define power:

 public static int power(int base, int exponent) { // TODO }

To receive full credit, you must implement an algorithm that calculates bⁿ with O(log(n)) worst-case run-time. You will only receive partial credit if your worst-case run-time is O(n).

Problem 3

Recursion can be a very powerful tool for solving difficult problems. Let's solve a problem using recursion. Minesweeper is a single-player game were the player is presented with a grid of "cells" like this:

Some of the cells contain "mines" and some don't. Clicking on a cell reveals whether the cell is a mine or not. If a player clicks on a mine, they lose. If the player clicks on a cell that is not a mine, the cells are revealed using an interesting algorithm. We are going to create and implement such an algorithm using recursion.

Here's the idea behind the algorithm. When a cell is clicked at some row, r, and column, c.

If (r, c) is not a valid row and column, do nothing. (The player didn't even click on the board.)

If (r, c) is not a covered cell, do nothing. (The player has already click the cell.)

If the cell at (r, c) is a mine, then show the entire board. (The game is over.)

If the cell at (r, c) is not a mine, count the number of adjacent cells that contain mines. There are 8 adjacent cells as diagonal cells count as adjacent. We will call the count the "mine count for the cell at (r, c)".

If the mine count for the cell at (r, c) is not zero, show this mine count instead of a covered cell and do steps 1 - 6 for cells at (r-1, c), (r+1, c), (r, c-1), and (r, c+1).

If the mine count for the cell at (r, c) is zero, do steps 1 - 6 for cells at (r-1, c), (r+1, c), (r, c-1), and (r, c+1).

The steps above can be implemented recursively. You'll need to identify the base cases and the recursive steps.

To implement this algorithm, we will need a game board. We'll use a 2D array like this: char[][] board = { { '*', '-', '-', '-', '-' }, { '*', '-', '*', '*', '-' }, { '*', '-', '-', '*', '-' }, { '*', '*', '*', '*', '-' }, { '-', '-', '-', '-', '*' }, };

For this board, '*' is a mine, and '-' is a covered cell. To use the checks for this assignment, please follow this convention. Then, define a "showMines" method in "RecursiveMethods" like this:

 public static void showMines(char[][] board, int row, int col) { \\ TODO code here... }

The board is the game board like the array shown above. The parameters row and col are the row and column for the cell to be revealed. The method showMines directly modifies the board, so the return for this method is void.

Here are some examples using the board above as input.

Calling showMines(board, 4, 1) modifies board to give:

 board = { { '*', '-', '-', '-', '-' }, { '*', '-', '*', '*', '-' }, { '*', '-', '-', '*', '-' }, { '*', '*', '*', '*', '-' }, { '2', '3', '3', '3', '*' }, };

Calling showMines(board, 2, 4) instead modifies board to give:

 board = { { '*', '3', '2', '2', '1' }, { '*', '4', '*', '*', '2' }, { '*', '6', '6', '*', '3' }, { '*', '*', '*', '*', '3' }, { '-', '-', '-', '-', '*' }, };

Calling showMines(board, 3, 2) instead modifies board to give:

 board = { { '*', '3', '2', '2', '1' }, { '*', '4', '*', '*', '2' }, { '*', '6', '6', '*', '3' }, { '*', '*', '*', '*', '3' }, { '2', '3', '3', '3', '*' }, };

For the last examples, note that (3, 2) is mine.

To help write your code, you may want to write a few helper methods for printing a 2D array, checking if (r, c) is a valid row and column, count adjacent mines for a give (r, c), etc. Feel free to create as many helper methods in the RecursiveMethods class as you want, just be sure that showMines is defined as above so that you can use the checks for this assignment.

Final Note

You MUST use recursion to solve the above three problems. You will not get credit for an iterative solution.