Recursion - Building Java Programs: A Back to Basics Approach - page 765

public static int digitSum(int n) {
if (n > 10) {
// base case (small number)
return n;
} else {
// recursive case (large number)
return n % 10 + digitSum(n / 10);
}
}
15. Sometimes the parameters that a client would like to pass to a method don't match the parameters that are best for
writing a recursive solution to the problem. What should a programmer do to resolve this issue?
16. The Fibonacci sequence is a sequence of numbers in which the first two numbers are 1 and each subsequent number
is the sum of the previous two Fibonacci numbers. The sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The follow-
ing is a correct, but inefficient, method to compute the n th Fibonacci number:
public static int fibonacci(int n) {
if (n <= 2) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}
The code shown runs very slowly for even relatively small values of n ; it can take minutes or hours to compute even
the 40th or 50th Fibonacci number. The code is inefficient because it makes too many recursive calls. It ends up
recomputing each Fibonacci number many times. Write a new version of this method that is still recursive and has
the same header but is more efficient. Do this by creating a helper method that accepts additional parameters, such as
previous Fibonacci numbers, that you can carry through and modify during each recursive call.
Section 12.4: Recursive Graphics
17. What is a fractal image? How does recursive programming help to draw fractals?
18. Write Java code to create and draw a regular hexagon (a type of polygon).
Exercises
1. Write a recursive method called starString that accepts an integer as a parameter and prints to the console a string
of stars (asterisks) that is 2 n (i.e., 2 to the n th power) long. For example,
• starString(0) should print * (because 2 0 == 1)
• starString(1) should print ** (because 2 1 == 2)
• starString(2) should print **** (because 2 2 == 4)
• starString(3) should print ******** (because 2 3 == 8)
• starString(4) should print **************** (because 2 4 == 16)
The method should throw an IllegalArgumentException if passed a value less than 0 .