CSCI 161 — Lab 12

Due: Friday, May 11th @ 11:59PM

Objectives

• Apply recursive thinking to solving problems

Overview

• Implement several methods which solve independent tasks which leverage courage
• Name your Java file Recursion.java

Required Methods

lengthOfNumber (10 points)

Determines the digit count of a non-negative number

Signature

static int lengthOfNumber (int n)

Parameter

• n a non-negative number

Examples

lengthOfNumber (9);    // returns 1
lengthOfNumber (1234); // returns 4
lengthOfNumber (92);   // returns 2
lengthOfNumber (0);    // returns 1

countCharInString (10 points)

Counts the number of occurrence of a character in a string

HINT: use substring() for recursive calls

Signature

static int countCharInString (char c, String s)

Parameters

• c character to find
• s string to search

Examples

countCharInString ('a', "hello");       // returns 0
countCharInString ('g', "programming"); // returns 2

gcd (15 points)

Computes the greatest common divisor of two numbers, x and y

• GCD(x,x) will always yield x
• GCD(x,y) will yield GCD(x - y, y) when x > y
• GCD(x,y) will yield GCD(x, y - x) when y > x

Signature

static int gcd (int x, int y)

Parameters

• x a number
• y a number

Examples

gcd (12, 18); // returns 6
gcd (73, 37); // returns 1

removeMatchingDigits (15 points)

Removes all occurrences of a digit from a number

Signature

static int removeMatchingDigits (int n, int digit)

Parameters

• n a number that contains only the digits 1 through 9
• digit a single digit number (not zero)

Examples

removeMatchingDigits (12345, 2); // returns 1345
removeMatchingDigits (12345, 5); // returns 1234
removeMatchingDigits (99999, 9); // returns 0
removeMatchingDigits (2111, 1);  // returns 2
removeMatchingDigits (323, 3);   // returns 2

fibonacci (20 points)

Returns the nth fibonacci number

https://en.wikipedia.org/wiki/Fibonacci_number

Signature

static int fibonacci (int n)

Parameter

• n a non-negative number between 0 and 20

Examples

fibonacci (0);  // returns 0
fibonacci (1);  // returns 1
fibonacci (2);  // returns 1
fibonacci (3);  // returns 2
fibonacci (10); // returns 55

isSorted (20 points)

Returns true if and only if the array a is sorted from indicies [low, high)

Hints:

• when there is zero or one elements in the range, it is sorted
• you may want to split the range in half
  • is the left half sorted?
  • is the right half sorted?
• do a single comparison in the function

Signature

static boolean isSorted (int[] a, int low, int high)

Parameters

• a an integer array
• low the lower (inclusive) bound of the range
• high the upper (exclusive) bound of the range

Examples

int[] a1 = { 2, 1, 4, 5 };
boolean r1 = isSorted (a1, 0, a1.length)
// r1 is false

int[] a2 = { 10, 15 };
boolean r2 = isSorted (a2, 0, a2.length)
// r2 is true

Submission

Submit the Java source code file on Autolab under the "Lab 12" assignment.

Grading

• 90 points will be awarded for passing the Autolab tests
• 10 points will be awarded for having a well-formatted, well-documented source code file. This includes your name, date, description, and comments throughout the program. This also includes other style requirements, such as method naming conventions. NOTE: The autograder will not display these points.
• NOTE: if your program does not compile/run, the highest score you will earn will be a 20/100