CSCI 162 — Lab 8

Due: Sunday November 25, 2018 @ 11:59PM

Recursion

You may ONLY talk with Professor Killian for this assignment. Any collaboration beyond that is CHEATING

All iteration must be done with recursion. Do NOT include any loops in your code.

Goals

Overview

You will write one Java program, named Recursion.java, with three recursive methods, one to solve each problem described below. Use the following function signatures:

public static String pattern (int n)

public static String hourglass (int n)

public static String commas (long n)

You may have extra private static methods in your Recursion class (helper functions), but you should NOT use any instance variables! All communication with the methods should be through parameters and return values.

Classes (other than the necessary Recursion class), arrays, loops, stacks, queues, pointers, and linked lists are inappropriate here and should not be used in the recursive methods. Do not use data structures beyond Strings in the hourglass program. Do not use any operations on Strings other than concatenation. In particular, do not use any substring or subscripting operations. Do not ask for a String's length. The autograder cannot detect this, but I will

Include comments at the top of your program and on any method other than main.

Pattern Specification

The "pattern" method accepts a single integer as a parameter. If that integer is less than 1, the method should return the error message "Argument must be >= 1". Otherwise, the method should return a String containing a pattern of integers as demonstrated in the table below. There is a space before each integer and a newline (\n) after each integer greater than 5. The underlines and boldface are hints to help you see that pattern and are not included in the String returned by your method. Your program should work for any positive integer, but because it prints \( 2^n - 1 \) numbers (plus spaces) for input \(n\), do not test it with anything larger than 10.

n what is printed
1 1
2 1 2 1
3 1 2 1 3 1 2 1
4 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

This produces a numeric pattern symmetric about n where each half before and after n is also symmetric around n - 1. The newline after printing any integer larger than 5 provides a nice line length and also makes the pattern of the bigger numbers along the right edge reading down. If you get the normal pattern, that will just happen. Don't think about it. Output for an input of 7 is:

 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6
 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7
 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6
 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

Approaching the Pattern Problem

In writing recursive methods, consider the base case. What is the base case here? It's the simple case that doesn't require another method call. For this problem, it's what happens when n is 1. Write that case and test it.

Now what happens if n is larger than 1?

Test your program thoroughly. You can test it exhaustively up to 10, but it should work for larger numbers.

Hourglass Specification

The "hourglass" method accepts a single integer as a parameter. If that integer is less than 1, the method should return the error message "Argument must be greater than or equal to 1". The hourglass base case with input 1 displays two lines with one star on each line * (note the following space). Otherwise, it prints a pattern of asterisks (*) as shown below for an argument of 4. Note that there are four stars (and spaces) on the first and last lines. Also note that each pattern ends with a final newline (\n).

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

Approaching the Hourglass Problem

Obtain the input and check its validity in the hourglass method that takes a single parameter.

Write a public static, recursive, helper method. There are many ways to write this method, but most of them involve having two parameters representing the number of stars and the number of spaces in front of the stars on the top and bottom lines. For the overall hourglass design, there are no spaces before the stars on the first and last lines.

It will be extremely helpful to write a helper method called printMany that takes in an integer count and a String "s". It "prints" (generates) count copies of "s" without finishing the line. You wouldn't normally write such a method recursively in Java, but this is recursion practice. Do even that recursively. No loops.

Commas Specification

Your "commas" method should take a long value and return a String of the value with commas separating segments of three digits as shown below. Use / and % to break the number apart. The method should deal with negative numbers, with numbers that are less than 1000, and with numbers that are greater than or equal to 1000. Note that to receive any credit, you must use a recursive method as outlined above.

You may NOT use NumberFormat or DecimalFormat or any other formating class. This is a recursion assignment.

Note also that the method is limited to numbers that are between \( -(2^{63}) \) and \( 2^{63} - 1 \). Values outside that range will not give correct results. Your program should not assume anything about this limit. That is, the program should work correctly with the types changed to a type that allows unlimited size numbers. Do not check the range.

Approaching the Commas Problem

Example Input and Output for Commas

Input Output
1024 1,024
42 42
0 0
-365 -365
-76543 -76,543
12345678 12,345,678
-1234567890123456789 -1,234,567,890,123,456,789
9223372036854775807 9,223,372,036,854,775,807
-9223372036854775808 -9,223,372,036,854,775,808

Main

main() should highlight what you used to test and evaluate your recursive methods.

Here's a simple method called shell which allows you to quickly test a method:

public static void shell() {
    Scanner sc = new Scanner(System.in);
    while (true) {
        System.out.print("==> ");
        String version = sc.next();
        if (version.equals("pattern")) {
            System.out.println(pattern(sc.nextInt()));
        } else if (version.equals("hourglass")) {
            System.out.print(hourglass(sc.nextInt()));
        } else if (version.equals("commas")) {
            System.out.println(commas(sc.nextLong()));
        } else if (version.equals("exit")) {
            break;
        } else {
            System.out.println("Available commands:");
            System.out.println("  pattern <n>");
            System.out.println("  hourglass <n>");
            System.out.println("  commas <n>");
            System.out.println("  exit");
        }
    }
    sc.close();
}

Submission

Submit this program as Lab 8: Recursion

Grading