Thinking Recursively with Java

10.4. Exercises

10-1.	Starting with the code in Figure 10-1, rewrite the methods length, concat, toString, and toCLString so that they operate iteratively without using recursion. Figure 10-6. The Compound class
10-2.	Suppose that someone has added the following method definition to the CLString class in Figure 10-1: private String mystery(CharCell list) { if (list == null) { return ""; } else { return mystery(list.link) + list.ch; } } What does the method mystery do? Can you duplicate the effect of this method without using recursion?
10-3.	Extend the definition of CLString so that it also implements the following methods from the standard String class: public char charAt(int index) public int indexOf(int ch) public CLString substring(int begin, int end)
10-4.	As presented in section 10.1, the CLString class is extremely inefficient in its use of space, since each character requires enough storage to hold not only the character but also a reference to the next cell in the linked list, which presumably requires even more space than the character does. To reduce this overhead, it is possible to define strings so that the chaining is done on the basis of character blocks rather than individual characters. Design a new string-like class that stores more than one character within each cell. Discuss the effect that this new representation has on the efficiency of the standard methods in ...