22.5. Lists

[Page 652]

Programming Exercises

Sections 19.2 “19.3

19.1	( Computing factorials ) Rewrite the factorial method in Listing 19.1 using iterations.
19.2*	( Fibonacci numbers ) Rewrite the fib method in Listing 19.2 using iterations. Hint To compute fib(n) without recursion, you need to obtain fib(n - 2) and fib(n - 1) first. Let f0 and f1 denote the two previous Fibonacci numbers. The current Fibonacci number would then be f0 + f1 . The algorithm can be described as follows : f0 = ; // For fib(0) f1 = 1 ; // For fib(1) for ( int i = 1 ; i <= n; i++) { currentFib = f0 + f1; f0 = f1; f1 = currentFib; } // After the loop, currentFib is fib(n)
19.3*	( Computing greatest common divisor using recursion ) The gcd(m, n) can also be defined recursively as follows: If m% n is , gcd (m, n) is n . Otherwise, gcd(m, n) is gcd(n, m % n) . Write a recursive method to find the GCD. Write a test program that computes gcd(24, 16) and gcd(255, 25) .
19.4	( Summing series ) Write a recursive method to compute the following series:
19.5	( Summing series ) Write a recursive method to compute the following series:
19.6**	( Summing the series ) Write a recursive method to compute the following series:
19.7*	( Fibonacci series ) Modify Listing 19.2, ComputeFibonacci.java, so that the program finds the number of times the fib method is called. Hint Use a static variable and increment it every time the method is called.

Section 19.4 Problem Solving Using Recursion

19.8**	( Printing the digits in an integer reversely ) Write a recursive method that displays an int value reversely on the console using the following header: public static void reverseDisplay( int value) For example, reverseDisplay(12345) displays 54321 .
[Page 653]
19.9**	( Printing the characters in a string reversely ) Write a recursive method that displays a string reversely on the console using the following header: public static void reverseDisplay(String value) For example, reverseDisplay("abcd") displays dcba .
19.10*	( Occurrences of a specified character in a string ) Write a recursive method that finds the number of occurrences of a specified letter in a string using the following method header: public static int count(String str, char a) For example, count("Welcome", 'e') returns 2.
19.11**	( Summing the digits in an integer using recursion ) Write a recursive method that computes the sum of the digits in an integer. Use the following method header: public static int sumDigits( long n) For example, sumDigits(234) returns

Section 19.5 Recursion Helper Methods

19.12**	( Printing the characters in a string reversely ) Rewrite Exercise 19.9 using a helper method to pass the substring high index to the method. The helper method header is: public static void reverseDisplay(String value, int high)
19.13**	( Finding the largest number in an array ) Write a recursive method that returns the largest integer in an array.
19.14*	( Finding the number of uppercase letters in a string ) Write a recursive method to return the number of uppercase letters in a string.
19.15*	( Occurrences of a specified character in a string ) Rewrite Exercise 19.10 using a helper method to pass the substring high index to the method. The helper method header is: public static int count(String str, char a, int high)
19.16*	( Finding the number of uppercase letters in an array ) Write a recursive method to return the number of uppercase letters in an array of characters. You need to declare the following two methods. The second one is a recursive helper method. public static int count( char [] chars) public static int count( char [] chars, int high)
19.17*	( Occurrences of a specified character in an array ) Write a recursive method that finds the number of occurrences of a specified character in an array. You need to declare the following two methods. The second one is a recursive helper method. public static int count( char [] chars, char ch) public static int count( char [] chars, char ch, int high)

---

[Page 654]

Sections 19.6 Tower of Hanoi

19.18*	( Towers of Hanoi ) Modify Listing 19.7, TowersOfHanoi.java, so that the program finds the number of moves needed to move n disks from tower A to tower B. (Hint: Use a static variable and increment it every time the method is called.)
19.19*	( Sierpinski triangle ) Revise Listing 19.8 to develop an applet that lets the user use the Increase and Decrease buttons to increase or decrease the current order by 1, as shown in Figure 19.8(a). The initial order is 0. If the current order is 0, the Decrease button is ignored. Figure 19.8. (a) Exercise 19.19 uses the Increase and Decrease buttons to increase or decrease the current order by 1. (b) Exercise 19.10 draws ovals using a recursive method.
19.20*	( Displaying circles ) Write a Java applet that displays ovals, as shown in Figure 19.8(b). The ovals are centered in the panel. The gap between two adjacent ovals is 10 pixels, and the gap between the panel and the largest oval is also 10.

Comprehensive

19.21***	( String permutation ) Write a recursive method to print all the permutations of a string. For example, for a string abc , the printout is abc acb bac bca cab cba Hint Declare the following two methods. The second is a helper method. public static void displayPermutation(String s) public static void displayPermutation(String s1, String s2) The first method simply invokes displayPermutation("", s) . The second method uses a loop to move a character from s2 to s1 and recursively invoke it with a new s1 and s2 . The base case is that s2 is empty and prints s1 to the console.
19.22***	( Creating a maze ) Write an applet that will find a path in a maze, as shown in Figure 19.9(a). The applet should also run as an application. The maze is represented by an 8 x 8 board. The path must meet the following conditions: The path is between the upper-left corner cell and the lower-right corner cell in the maze. [Page 655] The applet enables the user to insert or remove a mark on a cell. A path consists of adjacent unmarked cells. Two cells are said to be adjacent if they are horizontal or vertical neighbors, but not if they are diagonal neighbors. The path does not contain cells that form a square. The path in Figure 19.9(b), for example, does not meet this condition. (The condition makes a path easy to identify on the board.) Figure 19.9. The program finds a path from the upper-left corner to the bottom-right corner.
19.23***	( Koch snowflake fractal ) The text presented the Sierpinski triangle fractal. In this exercise, you will write an applet to display another fractal, called the Koch snowflake , named after a famous Swedish mathematician . A Koch snowflake is created as follows: It begins with an equilateral triangle, which is considered to be the Koch fractal of order (or level) 0, as shown in Figure 19.10(a). Figure 19.10. A Koch snowflake is a fractal starting with a triangle. Divide each line in the shape into three equal line segments and draw an outward equilateral triangle with the middle line segment as the base to create a Koch fractal of order 1, as shown in Figure 19.10(b). Repeat step 2 to create a Koch fractal of order 2, 3, and so on, as shown in Figure 19.10(c). [Page 656]