Recursion - Data Structures and Problem Solving Using Java - page 345

PROGRAMMING PROJECTS
7. 3 6

The method printReverse takes a Scanner as a parameter, prints each
line in the Scanner stream, and closes the Scanner when it is done.
However, the lines are to be output in reverse order of their occur-
rence. In other words, the last line is output first, and the first line is
output last. Implement printReverse without using any Collections
API or user-written containers. Do so by using recursion (in which
you output the first line AFTER recursively outputting the subsequent
lines in reverse).

Function findMaxAndMin , defined below is intended to return (in an
array of length 2) the maximum and minimum item (if arr.length is
1, the maximum and minimum are the same):

7. 3 7

// Precondition: arr.length >=1
// Postcondition: the 0th item in the return value is the maximum
// the 1st item in the return value is the minimum
public static double [ ] findMaxAndMin( double [ ] arr )

Write an appropriate private static recursive routine to implement
the public static driver findMaxAndMin declared above. Your recursive
routine must split a problem into roughly two halves, but should
never split into two odd-sized problems (in other words, a problem of
size 10 is to be split into 4 and 6, rather than 5 and 5).

The binomial coefficients C ( N, k ) can be defined recursively as
C ( N, 0) = 1, C ( N, N ) = 1 and, for 0 < k < N, C ( N, k ) = C ( N - 1, k ) +
C ( N - 1, k - 1). Write a method and give an analysis of the running
time to compute the binomial coefficients
a.

7. 3 8

Recursively

b. By using dynamic programming

Add a divide method to the Polynomial class in Exercise 3.33.
Implement divide using recursion.

7. 3 9

Implement the RSA cryptosystem with the library BigInteger class.

7. 4 0

Improve the TicTacToe class by making the supporting routines more
efficient.

7.41

Write routine getAllWords that takes as parameter a word and returns a
Set containing all the substrings of the word. The substrings do not
need to be real words, nor contiguous, but the letters in the substrings
must retain the same order as in the word. For instance, if the word is
cabb , words that set returned by getAllWords would be [ "" , " b " , " bb " ,
" a " , " ab " , " abb " , " c " , " cb " , " cbb " , " ca " , " cab " , " cabb " ].

7.42