- As discussed in the prelab,
computing a positive integer power of a number is easily seen as a recursive
File Power.java contains a main program
that reads in integers base and exp and calls method power
to compute baseexp. Fill in the code for power
to make it a recursive method to do the power computation. The comments
- The Fibonacci sequence is a well-known mathematical sequence in which
each term is the sum of the two previous terms. More specifically, if fib(n) is
the nth term of the sequence, then the sequence can be defined as follows:
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) n>1
For example, the first eight elements of the sequence are 0,1,1,2,3,5,8,13.
Because the Fibonacci sequence is defined recursively, it is natural to write
a recursive method to determine the nth number in the sequence. File
Fib.java contains the skeleton for a program that reads an integer n
from and computes and prints the nth Fibonacci number.
Save this file to your directory. Following the
specification above, fill in the code for method fib so that it
recursively computes and returns the nth number in the sequence.
Printing a string backwards can be done iteratively or recursively.
To do it recursively, think of the following specification:
If s contains any characters (i.e., is not the empty string)
- print the last character in s
- print s' backwards, where s' is s without its last character
File Backwards.java contains a program
that prompts the user for a string, then calls method printBackwards
to print the string backwards. Save this file to your directory and
fill in the code for printBackwards
using the recursive strategy outlined above.
that for a String s in Java,
So if s="happy", s.length=5, s.charAt(1)=a, and
s.substring(2,4) = "pp".
- s.length() returns the number of charaters in s
- s.charAt(i) returns the ith character of s, 0-based
- s.substring(i,j) returns the substring that starts with the ith
character of s and ends with the j-1st character of s (not
the jth!), both 0-based.
- A palindrome is a string that is the same forward and backward.
In Chapter 3 you saw a program that uses a loop to determine whether a
string is a palindrome. However,
it is also easy
to define a palindrome recursively as follows:
- A string containing fewer than 2 letters is always a palindrome.
- A string containing 2 or more letters is a palindrome if
- its first and last letters are the same, and
- the rest of the string (without the first and last letters) is also
Write a program that prompts for and reads in a string, then prints a message
saying whether it is a palindrome. Your main method should read the string
and call a recursive (static) method palindrome that takes a string and returns
true if the string is a palindrome, false otherwise.
One algorithm for converting a base 10 number to base b involves
repeated division by the base b. Initially one divides the number by
b. The remainder from this division is the units digit (the rightmost digit)
in the base b representation of the number (it is the part of the
number that contains no powers
of b). The quotient is then divided by b on
the next iteration. The remainder from this division gives the next
base b digit from the right. The quotient from this division is used
in the next iteration. The algorithm stops when the quotient is 0. Note
that at each iteration the remainder from the division is the next base b
digit from the right -- that is, this algorithm finds the digits for the
base b number in reverse order.
Here is an example for converting 30 to base 4:
30/4 = 7 2
7/4 = 1 3
1/4 = 0 1
The answer is read bottom to top in the remainder column, so
30 (base 10) = 132 (base 4).
Think about how this is recursive in nature:
If you want to convert x (30 in our example) to
base b (4 in our example), the rightmost digit is the remainder x % b.
To get the rest of the digits, you perform the same process on
what is left; that is, you
convert the quotient x / b to base b. If x / b is 0, there is no rest;
x is a single base b digit and that digit is x % b (which also is
The file BaseConversion.java
contains the shell of a method convert to do the base
conversion and a main method to test the conversion. Note
that the convert
method returns a string representing the base b number. This means
in the base case, when the remainder is what is
to be returned, it must be converted to a String object by concatenating
it with a null string. Similarly, in the recursive case
the result of the recursive call will be concatenated with the remainder.
Fill in the code for convert and the call in the main method.
Here is some data to test your program on:
- Number: 89 Base: 2 ---> should print 1011001
- Number: 347 Base: 5 ---> should print 2342
- Number: 3289 Base: 8 ---> should print 6331