## 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*) = 2*T*(*n*/2) + 1*T*(*n*) = 2*T*(*n*/2) +*n**T*(*n*) = 4*T*(*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*F*recursive calls to_{n}`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 log_{2}*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.