Exercises for Chapter 15
Define descendent recursively.
Define the format of binary integers (sequences of 0 s and 1 s) recur-
Define the format of Java identifiers recursively.
Define a list of integers separated by commas recursively.
2. Write a recursive definition for the product x*y of two integers x and y ,
where y≥0 .
3. Write a recursive definition for exponentiation x y of two integers x and y ,
where y≥0 .
4. Write a recursive function to sum the values in a range. With the specification
given for it, the values have to be summed from largest to smallest.
/** = sum of integers in the range 0..n , for n ≥ -1 */
public static int sum( int n)
5. The function of the previous exercise has a recursive call that is not tail-recur-
sive. The way to change the function so that it will be tail-recursive is to add a
parameter. Write the following function so that the recursive call is tail recursive.
/** = x + ( sum of integers in the range 0..n) , for n ≥ -1 */
public static int sum( int x, int n)
6. Rewrite the function of the previous exercise to eliminate the tail-recursive
call using the technique of Sec. 15.3.4.
7. Implement the inefficient function to calculate Fibonacci numbers (see Sec.
15.2.3) and calculate some Fibonacci numbers to see how long it takes. Try calls
like Fib(10) , Fib(20) , Fib(30) , ... until you get some sense of how inefficient
this function is.
8. Function fib of the previous exercise is extremely inefficient, requiring time
proportional to F n to calculate fib(n) . The way to get a more efficient function
is to add parameters to the function, as illustrated below. Write the function body.
Make sure that any recursive calls are tail recursive.
/** = F n , for 0<n , given that 1≤k≤n,a=F k , and b=F k-1 */
public static int FibLinear( int n, int k, int a, int b)
9. In Exercise 8, you wrote a function whose only call is tail recursive. Use the
method of Sec. 15.3.4 to eliminate the tail-recursion from that function.
10. Write a recursive boolean function that tells whether a String contains a
Write a recursive function removeDups that removes duplicate adjacent