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.
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.
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.
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.
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.
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.
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.
