This chapter is from the book
This chapter is from the book
This chapter is from the book
Exercises
2.3.1 What happens if you call factorial() with a negative value of n? With a large value of, say, 35?
2.3.2 Write a recursive function that takes an integer n as its argument and returns ln (n !).
2.3.3 Give the sequence of integers printed by a call to ex233(6):
public static void ex233(int n)
{
if (n <= 0) return;
StdOut.println(n);
ex233(n-2);
ex233(n-3);
StdOut.println(n);
}2.3.4 Give the value of ex234(6):
public static String ex234(int n)
{
if (n <= 0) return "";
return ex234(n-3) + n + ex234(n-2) + n;
}2.3.5 Criticize the following recursive function:
public static String ex235(int n)
{
String s = ex235(n-3) + n + ex235(n-2) + n;
if (n <= 0) return "";
return s;
}Answer: The base case will never be reached because the base case appears after the reduction step. A call to ex235(3) will result in calls to ex235(0), ex235(-3), ex235(-6), and so forth until a StackOverflowError.
2.3.6 Given four positive integers a, b, c, and d, explain what value is computed by gcd(gcd(a, b), gcd(c, d)).
2.3.7 Explain in terms of integers and divisors the effect of the following Euclid-like function:
public static boolean gcdlike(int p, int q)
{
if (q == 0) return (p == 1);
return gcdlike(q, p % q);
}2.3.8 Consider the following recursive function:
public static int mystery(int a, int b)
{
if (b == 0) return 0;
if (b % 2 == 0) return mystery(a+a, b/2);
return mystery(a+a, b/2) + a;
}What are the values of mystery(2, 25) and mystery(3, 11)? Given positive integers a and b, describe what value mystery(a, b) computes. Then answer the same question, but replace + with * and return 0 with return 1.
2.3.9 Write a recursive program Ruler to plot the subdivisions of a ruler using StdDraw, as in PROGRAM 1.2.1.
2.3.10 Solve the following recurrence relations, all with T(1) = 1. Assume n is a power of 2.
T(n) = T(n/2) + 1
T(n) = 2T(n/2) + 1
T(n) = 2T(n/2) + n
T(n) = 4T(n/2) + 3
2.3.11 Prove by induction that the minimum possible number of moves needed to solve the towers of Hanoi satisfies the same recurrence as the number of moves used by our recursive solution.
2.3.12 Prove by induction that the recursive program given in the text makes exactly Fn recursive calls to fibonacci(1) when computing fibonacci(n).
2.3.13 Prove that the second argument to gcd() decreases by at least a factor of 2 for every second recursive call, and then prove that gcd(p, q) uses at most 2 log2 n + 1 recursive calls where n is the larger of p and q.
2.3.14 Modify Htree (PROGRAM 2.3.4) to animate the drawing of the H-tree. Next, rearrange the order of the recursive calls (and the base case), view the resulting animation, and explain each outcome.
)