Problem Set 12
Summary
For this problem set, we'll be focusing on recursive problems and solutions. Each method, with the exception of the main
method, is declared for you. It is your responsibility to implement each method, and test it thoroughly.
Requirements
Create a repository called
pset-12
.Mark your repository as private, and add me as a collaborator (
ryanjwilson
).Pull down the skeleton repository containing starter code.
Solve each of the exercises, placing each solution in the appropriate method.
Add, commit, and push your code to your
pset-12
repository.
Exercises
The specifications for each exercise are outlined below. Your job is to write code that meets the stated requirements, and matches my output exactly. Work through these exercises on your own. Experiment, make mistakes, ask questions, and fix your mistakes. It's the only way to get good at programming.
Previously, your output was printed to the console. This time, though, you'll be using return statements. To clarify, nothing should be printed to the console and you don't need to use a Scanner
at all. Correct answers that are printed to the console instead of returned will not be considered.
As a final note, do not modify the method signatures. You can write your code inside of the method bodies, but the names, access modifiers, return types, and parameters must not be altered.
To be clear, it is possible to craft solutions to each of these problems using iteration. There are also certain built-in methods that may perform the computations for you. Neither of those are the purpose of this problem set. You must use recursion for each of your solutions!
Exercise 1
Given an integer, n
, compute and return the factorial of n
(i.e., n!
). Return -1
if any of the following conditions is not met.
n
must be greater than0
.
Here are a few sample calls to the factorial
method, along with their expected outputs. It is your responsibility to make sure your code works as expected for all possible inputs, not just these three.
factorial(1) → 1
factorial(2) → 2
factorial(3) → 6
Exercise 2
The Fibonacci sequence is a famous bit of mathematics, and it happens to have a recursive definition. The first two values in the sequence are 0
and 1
, which are essentially the two base cases. Each subsequent value is the sum of the previous two, so the sequence looks like this: 0, 1, 1, 2, 3, 5, 8
, and so on. Compute and return the n
th Fibonacci number, with n = 0
representing the start of the sequence. Return -1
if any of the following conditions is not met.
n
must be greater than or equal to0
.
Here are a few sample calls to the fibonacci
method, along with their expected outputs. It is your responsibility to make sure your code works as expected for all possible inputs, not just these three.
fibonacci(0) → 0
fibonacci(1) → 1
fibonacci(2) → 1
Exercise 3
Consider a triangle made of blocks. The topmost row has 1
block; the next row down has 2
blocks; the next row down has 3
blocks; and so on, and so forth. Compute the total number of blocks in a triangle with a specified number of rows
. Return -1
if any of the following conditions is not met.
rows
must be greater than or equal to0
.
Here are a few sample calls to the triangle
method, along with their expected outputs. It is your responsibility to make sure your code works as expected for all possible inputs, not just these three.
triangle(0) → 0
triangle(1) → 1
triangle(2) → 3
Exercise 4
Given a non-negative integer, n
, return the sum of its digits. Return -1
if any of the following conditions is not met.
n
must be a non-negative integer.
Here are a few sample calls to the sumDigits
method, along with their expected outputs. It is your responsibility to make sure your code works as expected for all possible inputs, not just these three.
sumDigits(126) → 9
sumDigits(49) → 13
sumDigits(12) → 3
Exercise 5
Given a base and exponent, compute the value of base raised to the power of exponent. Return -1 if any of the following conditions is not met.
base
must be greater than or equal to1
.exponent
must be greater than or equal to1
.
Here are a few sample calls to the powerN
method, along with their expected outputs. It is your responsibility to make sure your code works as expected for all possible inputs, not just these three.
powerN(3, 1) → 3
powerN(3, 2) → 9
powerN(3, 3) → 27
Exercise 6
Given a string, text
, build a new string where all of the lowercase x
characters are changed to lowercase y
characters. Return null
if any of the following conditions is not met.
text
must not benull
.
Here are a few sample calls to the changeXY
method, along with their expected outputs. It is your responsibility to make sure your code works as expected for all possible inputs, not just these three.
changeXY("codex") → "codey"
changeXY("xxhixx") → "yyhiyy"
changeXY("xhixhix") → "yhiyhiy"
Exercise 7
Given an array of integer values, data
, compute the number of times the value 11
appears in the array. We'll use the convention of considering only the part of the array that begins at the given index
and continues through the end of the array. Return -1
if any of the following conditions is not met.
data
must not benull
.index
must be greater than or equal to0
.index
must not exceed the bounds of the array.
Here are a few sample calls to the array11
method, along with their expected outputs. It is your responsibility to make sure your code works as expected for all possible inputs, not just these three.
array11([1, 2, 11], 0) → 1
array11([11, 11], 0) → 2
array11([1, 2, 3, 4], 0) → 0
Exercise 8
Given a string, text
, and a non-empty substring, sub
, compute the number of times that sub
appears in text
without instances of sub
overlapping each other. Return -1 if any of the following conditions is not met.
text
must not benull
.sub
must not benull
.sub
must be non-empty.
Here are a few sample calls to the strCount
method, along with their expected outputs. It is your responsibility to make sure your code works as expected for all possible inputs, not just these three.
strCount("catcowcat", "cat") → 2
strCount("catcowcat", "cow") → 1
strCount("catcowcat", "dog") → 0
Exercise 9
Given a string, text
, and non-empty substring, sub
, determine whether or not at least n
copies of sub
appear in text
, allowing for the possibility that instances of sub
may overlap each other. Return false
if any of the following conditions is not met.
text
must not benull
.sub
must not benull
.sub
must be non-empty.n
must be greater than or equal to0
.
Here are a few sample calls to the strCopies
method, along with their expected outputs. It is your responsibility to make sure your code works as expected for all possible inputs, not just these three.
strCopies("catcowcat", "cat", 2) → true
strCopies("catcowcat", "cow", 2) → false
strCopies("catcowcat", "cow", 1) → true
Exercise 10
Given a string, text
, and a non-empty substring, sub
, return the length of the largest substring that starts and ends with sub
. Return -1
if any of the following conditions is not met.
text
must not benull
.sub
must not benull
.sub
must be non-empty.
Here are a few sample calls to the strDist
method, along with their expected outputs. It is your responsibility to make sure your code works as expected for all possible inputs, not just these three.
strDist("catcowcat", "cat") → 9
strDist("catcowcat", "cow") → 3
strDist("cccatcowcatxx", "cat") → 9
Deliverables
Submit your repository URL.
Your program output should meet each of the requirements, and should account for test cases above and beyond those provided in the sample executions.
Deadline
All submissions are due on Canvas by 11:59pm on Sunday, March 7, 2021.
Last updated
Was this helpful?