Note: For programming exercises,first draw a UML class diagram describing all classes and their inheritance relationships and/or associations.
1.Java Concept Matching.
Match each of the following Recursion concepts.
iteration
using a loop structure for repetition
recursion
using a method that calls itself to perform repetition
recursive method
a method that calls itself
recursive definition
a sequential definition with a base case or multiple base cases, and then a recursive case that uses one or more earlier elements of the sequence to define the current element of the sequence
base case
a case where the method doesn’t call itself
recursive case
a condition where the method calls itself.
head
the first element of a string or an array
tail
everything after the first element of a string or an array
tail recursive
a recursive method where the only call to itself is the last call in the method.
nontail recursive
a recursive method that has a recursive call that is not the last call in the method.
2.Call Stack.
Describe how the method call stack is used during a method call and return.
3.Recursion Vs. Iteration.
Why is a recursive algorithm generally less efficient than an iterative algorithm?
4.Tree Recursion.
A tree, such as a maple tree or pine tree, has a recursive structure. Describe how a tree’s structure displays self-similarity and divisibility.
Writing Recursive Methods.
Each of the problems that follow asks you to write a recursive method. Of course, as you are developing the method in a stepwise fashion, you should test it. Here’s a simple application program that you can use for this purpose:
public class MethodTester {
public static void countdown(int i) {
if(i <= 0) {
System.out.println("Blastoff!");
return;
}
System.out.println(i);
countdown(i-1);
}
public static void main(String args[]) {
countdown(10);
}
}
Just replace the countdown() method with your method. Note that you must declare your method static if you want to call it directly from main() as we do here.
5.Recursive Array Print.
Write a recursive method to print each element of an array of double.
6.Reverse Recursive Array Print.
Write a recursive method to print each element of an array of double from the last to the first element.
7.Recursive Array To Phrase.
Write a recursive method that will concatenate the elements of an array of String into a single String delimited by blanks.
8.Recursive Odd Print.
Write a recursive method that is passed a single int parameter, \(N \geq 0\text{,}\) and prints all the odd numbers between 1 and N.
9.Recursive Even Countdown.
Write a recursive method that takes a single int parameter \(N \geq 0\) and prints the sequence of even numbers between N down to 0.
10.Recursive Count By Ten.
Write a recursive method that takes a single int parameter \(N \geq 0\) and prints the multiples of 10 between 0 and N.
11.Recursive Ramp.
Write a recursive method to print the following geometric pattern:
#
# #
# # #
# # # #
# # # # #
12.Recursive Patterns.
Write recursive methods to print each of the following patterns.
Write a recursive method to print all multiples of M up to M * N.
14.Recursive Grade Sum.
Write a recursive method to compute the sum of grades stored in an array.
15.Recursive Count Substring.
Write a recursive method to count the occurrences of a substring within a string.
16.Recursive Tag Removal.
Write a recursive method to remove the HTML tags from a string.
17.Recursive Shift Decode.
Implement a recursive version of the Caesar.decode() method from Chapter 8.
18.Recursive Fibonacci.
The Fibonacci sequence (named after the Italian mathematician Leonardo of Pisa, ca. 1200) consists of the numbers 0,1,1,2,3,5,8,13,… in which each number (except for the first two) is the sum of the two preceding numbers. Write a recursive method fibonacci(N) that prints the first N Fibonacci numbers.
19.Recursive String Rotate.
Write a recursive method to rotate a String by N characters to the right. For example, rotateR("hello", 3) should return “llohe.”
20.Recursive Left Rotate.
Write a recursive method to rotate a String by N characters to the left. For example, rotateL("hello", 3) should return “lohel.”
21.Recursive Binary to Decimal.
Write a recursive method to convert a String representing a binary number to its decimal equivalent. For example, binTodecimal("101011") should return the int value 43.
22.Recursive Palindrome Detector.
A palindrome is a string that is equal to its reverse— “mom,” “i,” “radar” and “able was i ere i saw elba.” Write a recursive boolean method that determines whether its String parameter is a palindrome.
23.Recursive Binary Tree.
Challenge: Incorporate a drawBinaryTree() method into the RecursivePatterns program. A level-one binary tree has two branches. At each subsequent level, two smaller branches are grown from the endpoints of every existing branch. The geometry is easier if you use 45-degree angles for the branches. The picture above shows a level-four binary tree drawn upside down.
24.Recursive Towers of Hanoi.
Challenge: Towers of Hanoi. According to legend, some Buddhist monks were given the task of moving 64 golden disks from one diamond needle to another needle, using a third needle as a backup. To begin with, the disks were stacked one on top of the other from largest to smallest (Fig. 12.37). The rules were that only one disk can be moved at a time and that a larger disk can never go on top of a smaller one. The end of the world was supposed to occur when the monks finished the task! Write a recursive method, move(int N, char A, char B, char C), that will print out directions the monks can use to solve the towers of Hanoi problem. For example, here’s what it should output for the three-disk case, move(3, "A", "B", "C"):
\caption{The towers of Hanoi problem. Move all the disks from needle A to needle B. Only one disk can be moved at a time, and a larger disk can never go on top of a smaller one. }
Move 1 disk from A to B.
Move 1 disk from A to C.
Move 1 disk from B to C.
Move 1 disk from A to B.
Move 1 disk from C to A.
Move 1 disk from C to B.
Move 1 disk from A to B.
