Recursive Program:Programming Assignment 2

You will implement and test 4 short recursive methods. With the proper

use of recursion, none of these methods should require more than a dozen

lines of code. Non-recursive methods receives 0 credit!!!

Purposes:

Ensure that you can write and test small recursive methods.

Your program file name must be AssignmentTwo.java. This program should

contain 4 recursive methods and your main method to test the four recursive

methods.

You may ask general questions from other students, tutors and your instructor, and

those students may answer questions with pencil and paper. But do not look at

program files or other students’ solutions to any homework problems. Do not write

any code in Canvas discussion threads.

1. Triangle Pattern

public void triangle(int m, int n)

/* Precondition: m <= n* Postcondition: The method should print a pattern of 2*(n-m+1) lines* to the standard output. The first line contains m asterisks, the next* line contains m+1 asterisks, and so on up to a line with n asterisks.* Then the pattern is repeated backwards, going n back down to m.* Example output: triangle(3, 5) will print this:*************************/Hint: Only one of the arguments changes in the recursive call. Which one?Test your program with following inputs:triangle(4, 8)triangle(5,5)triangle(3,6)triangle(6, 8)2. Section Numberspublic void numbers(String prefix, int levels)The method prints output consisting of the String prefix followed by "sectionnumbers" of the form 1.1., 1.2., 1.3., and so on. The levels argument determines howmay levels the section numbers have. For example, if levels is 2, then the sectionnumbers have the form x.y. If levels is 3, then section numbers have the form x.y.z.The digits permitted in each level are always '1' through '9'. As an example, if prefixis the string "THERBLIG" and levels is 2, then the method would start by printing:THERBLIG1.1.THERBLIG1.2.THERBLIG1.3.and end by printing:THERBLIG9.7.THERBLIG9.8.THERBLIG9.9.The stopping case occurs when levels reaches zero (in which case the prefix isprinted once by itself followed by nothing else).The Java String class has many manipulation methods, but you'll need only theability to make a new string which consists of prefix followed by another character(such as '1') and a period ('.'). If s is the String that you want to create and c is thedigit character (such as '1'), then the following statement will correctly form s:s = prefix + c + '.';This new String s can be passed as a parameter to recursive calls of the method.Test your method with following inputs:numbers(���EPISODE��� , 3)numbers(���ERA���, 4)numbers(���Passage���, 1)3. A Teddy Bear PicnicThis question involves a game with teddy bears. The game starts when I give yousome bears. You can then give back some bears, but you must follow these rules(where n is the number of bears that you have):1. If n is even, then you may give back exactly n/2 bears.2. If n is divisible by 3 or 4, then you may multiply the last two digits of n andgive back this many bears. (By the way, the last digit of n is n%10, and thenext-to-last digit is ((n%100)/10).3. If n is divisible by 5, then you may give back exactly 42 bears.The goal of the game is to end up with EXACTLY 42 bears.For example, suppose that you start with 250 bears. Then you could make thesemoves:�� --Start with 250 bears.�� --Since 250 is divisible by 5, you may return 42 of the bears, leaving you with 208bears.�� --Since 208 is even, you may return half of the bears, leaving you with 104 bears.�� --Since 104 is even, you may return half of the bears, leaving you with 52 bears.�� --Since 52 is divisible by 4, you may multiply the last two digits (resulting in 10)and return these 10 bears. This leaves you with 42 bears.�� --You have reached the goal!Write a recursive method to meet this specification:public boolean bears(int n)// Precondition: n>0

// Postcondition: A true return value means that it is possible to win // the bear

game by starting with n bears. A false return value means that

// it is not possible to win the bear game by starting with n bears. // Examples:

// bear(250) is true (as shown above)

// bear(42) is true

// bear(84) is true

// bear(53) is false

// bear(41) is false

// bear(854) is ?

// bear( 1011) is ?

Hint: To test whether n is even, use the expression ((n % 2) == 0).

4. Find Longest Repeated Pattern

public int findLongest(char c, String s, int length)

Given a String, find the longest sequence of matching characters in that String and

return that int length. For instance, ���aaabbccccccdde��� has 6 c���s so the method would

return 6

Call this method passing it the first character in the String, the rest of the String and

1, as in

findLongest(���a���, s, 1)

length represents the longest matching sequence found so far, which is 1 because

we found ���a���

Base case: if length==0 or length==1 return the length of s

Recursive cases: if c matches the 0th character of s, then we extend the sequence,

return the value of the recursive call with c, the rest of s after the 0th character, and

length+1

else no match, return whichever is larger, length (the length we found of char c up to

this point in s), or the value returned by recursively calling the method with the 0th

character of s, the rest of s, and 1 as we are starting over

Example: ���aaabbccccccdde���

Call the method with ���a���, ���aabbccccccdde���, 1

First character matches, so call with ���a���, ���abbccccccdde���, 2

First character matches, so call with ���a���, ���bbccccccdde, 3

No match, so return max(3, call with ���b���, ���bccccccdde���, 1)

First character matches, so call with ���b���, ���ccccccdde, 2

No match, so return max(2, call with ���c���, ���cccccdde���, 1)

First character matches, so call with ���c���, ���ccccdde���, 2

���

Eventually these calls return 6 (6 c���s found)

Return max(2, 6)

Return max(3, 6)

Run your program on the following inputs.

���aabbbcddddddeefffghiii���, ���19855aa00000cc24443bbb��� ,

���33335557i322k555554p���,

���2oo88rrrrr55ttyuuuuuuuuuuuuuuu44uuuuuuuuu4u444uuuuuuuuuuuuuuu���

Turn in the following

Cover page (page 1): Your name, assignment number, assignment title, and due

date.

One page abstract (page 2): Describe the four problems in your own words

(descriptions are given in the lab document), explain your recursive algorithm

design, and observations. Make sure to check spellings and grammar. The

abstract should be typed in Times New Roman style font with single spacing and

the font size of 12.

Source Program(s): Turn in Java source code AssignmentTwo.java. Your

program should be properly indented and commented with each method with

JavaDoc pre/post conditions.

Outputs: Outputs of all test cases in a PDF. Test cases are given to you in the

lab document. All outputs should be properly labeled identifying different

methods and their inputs.

Programming Assignment 2 You will implement and test 4 short recursive methods. With the proper use

of recursion, none of these methods should require more than a dozen lines of code. Non-recursive methods receives

0 credit!!! Purposes: Ensure that you can write and test small recursive methods. Your program

file name must be AssignmentTwo.java. This program should contain 4 recursive methods and your main method to test

the four recursive methods. You may ask general questions from other students, tutors and your instructor,

and those students may answer questions with pencil and paper. But do not look at program files or other

students’ solutions to any homework problems. Do not write any code in Canvas discussion threads.

1. Triangle Pattern public void triangle(int m, int n) /*

Precondition: m <= n * Postcondition: The method should print a pattern of 2*(n-m+1)lines * to the standard output. The first line contains m asterisks, the next* line contains m+1 asterisks, and so on up to a line with nasterisks. * Then the pattern is repeated backwards, going n back down to m.* Example output: triangle(3, 5) will print this:*** **** ********** **** ****/ Hint: Only one of the arguments changes in the recursive call. Which one? Test your program withfollowing inputs: triangle(4, 8) triangle(5,5) triangle(3,6) triangle(6, 8) 2. Section Numbers public void numbers(String prefix, int levels) The method prints output consisting ofthe String prefix followed by "section numbers" of the form 1.1., 1.2., 1.3., and so on. The levelsargument determines how may levels the section numbers have. For example, if levels is 2, then the sectionnumbers have the form x.y. If levels is 3, then section numbers have the form x.y.z. The digits permitted ineach level are always '1' through '9'. As an example, if prefix is the string "THERBLIG" and levels is2, then the method would start by printing: THERBLIG1.1. THERBLIG1.2. THERBLIG1.3. andend by printing: THERBLIG9.7. THERBLIG9.8. THERBLIG9.9. The stopping case occurs when levelsreaches zero (in which case the prefix is printed once by itself followed by nothing else). The Java String classhas many manipulation methods, but you'll need only the ability to make a new string which consists ofprefix followed by another character (such as '1') and a period ('.'). If s is the String that youwant to create and c is the digit character (such as '1'), then the following statement willcorrectly form s: s = prefix + c + '.'; This new String s can be passedas a parameter to recursive calls of the method. Test your method with following inputs: numbers(���EPISODE���, 3) numbers(���ERA���, 4) numbers(���Passage���, 1) 3. A Teddy Bear Picnic This question involves a gamewith teddy bears. The game starts when I give you some bears. You can then give back some bears, but youmust follow these rules (where n is the number of bears that you have): 1. If n is even, then you maygive back exactly n/2 bears. 2. If n is divisible by 3 or 4, then you may multiply the lasttwo digits of n and give back this many bears. (By the way, the last digit of n is n%10, andthe next-to-last digit is ((n%100)/10). 3. If n is divisible by 5, then you may give back exactly 42bears. The goal of the game is to end up with EXACTLY 42 bears. For example, suppose that you start with250 bears. Then you could make these moves: �� --Start with 250 bears. �� --Since 250 is divisibleby 5, you may return 42 of the bears, leaving you with 208 bears. �� --Since 208 is even, youmay return half of the bears, leaving you with 104 bears. �� --Since 104 is even, you may return halfof the bears, leaving you with 52 bears. �� --Since 52 is divisible by 4, you may multiplythe last two digits (resulting in 10) and return these 10 bears. This leaves you with 42 bears. ��--You have reached the goal! Write a recursive method to meet this specification: public boolean bears(int n) // Precondition: n>0 // Postcondition: A true return value means that it is

possible to win // the bear game by starting with n bears. A false return value

means that // it is not possible to win the bear game by starting with

n bears. // Examples: // bear(250) is true (as shown

above) // bear(42) is true // bear(84)

is true // bear(53) is false // bear

(41) is false // bear(854) is ? // bear( 1011) is ? Hint: To test whether n is

even, use the expression ((n % 2) == 0). 4. Find Longest Repeated Pattern

public int findLongest(char c, String s, int length) Given a String, find the longest sequence

of matching characters in that String and return that int length. For instance, ���aaabbccccccdde��� has 6

c���s so the method would return 6 Call this method passing it the first character in the String, the

rest of the String and 1, as in findLongest(���a���, s, 1) length represents the longest

matching sequence found so far, which is 1 because we found ���a��� Base case: if length==0 or

length==1 return the length of s Recursive cases: if c matches the 0th character of s, then

we extend the sequence, return the value of the recursive call with c, the rest of s after

the 0th character, and

length+1 else no match, return whichever is larger, length (the length we found of char c up to

this point in s), or the value returned by recursively calling the method with the 0th character of

s, the rest of s, and 1 as we are starting over Example: ���aaabbccccccdde���

Call the method with ���a���, ���aabbccccccdde���, 1 First character matches, so call with ���a���, ���abbccccccdde���,

2 First character matches, so call with ���a���, ���bbccccccdde, 3 No match, so return max(3, call

with ���b���, ���bccccccdde���, 1) First character matches, so call with ���b���, ���ccccccdde, 2 No match,

so return max(2, call with ���c���, ���cccccdde���, 1) First character matches, so call with ���c���, ���ccccdde���,

2 ��� Eventually these calls return 6 (6 c���s found) Return max(2, 6) Return max(3, 6)

Run your program on the following inputs. ���aabbbcddddddeefffghiii���, ���19855aa00000cc24443bbb��� ,

���33335557i322k555554p���, ���2oo88rrrrr55ttyuuuuuuuuuuuuuuu44uuuuuuuuu4u444uuuuuuuuuuuuuuu��� Turn in the following

Cover page (page 1): Your name, assignment number, assignment title, and due date. One page abstract (page 2): Describe the four problems in your own words

(descriptions are given in the lab document), explain your recursive algorithm design, and observations. Make sure to check spellings and grammar. The abstract should

be typed in Times New Roman style font with single spacing and the font size of 12. Source Program(s): Turn in Java source code AssignmentTwo.java. Your program

should be properly indented and commented with each method with JavaDoc pre/post conditions. Outputs: Outputs of all test cases in a PDF. Test cases are given to you

in the lab document. All outputs should be properly labeled identifying different methods and their inputs.