Java Reference
In-Depth Information
c. Infinite recursion
d. Recursive helper method
Exercise R13.2. Outline, but do not implement, a recursive solution for
finding the smallest value in an array.
Exercise R13.3. Outline, but do not implement, a recursive solution for
sorting an array of numbers. Hint: First find the smallest value in the array.
Exercise R13.4. Outline, but do not implement, a recursive solution for
generating all subsets of the set {1, 2, ș , n}.
Exercise R13.5. Exercise P13.12 shows an iterative way of generating
all permutations of the sequence (0, 1, ș , nɨ1). Explain why the
algorithm produces the correct result.
Exercise R13.6. Write a recursive definition of x
n
, where nʏ0, similar to
the recursive definition of the Fibonacci numbers. Hint: How do you
compute x
n
from x
nČ1
? How does the recursion terminate?
Exercise R13.7. Improve upon Exercise R13.6 by computing x
n
as (x
n/2
)
2
if n is even. Why is this approach significantly faster? (Hint: Compute
x
1023
and x
1024
both ways.)
Exercise R13.8. Write a recursive definition of n!=1¶2¶ș¶n, similar
to the recursive definition of the Fibonacci numbers.
Exercise R13.9. Find out how often the recursive version of
fib
calls
itself. Keep a static variable
fibCount
and increment it once in every
call of
fib
. What is the relationship between
fib(n)
and
fibCount
?
Exercise R13.10. How many moves are required in the "Towers of
Hanoi" problem of Exercise P13.13 to move n disks? Hint: As explained
in the exercise,
moves (1) = 1
moves ( n ) = 2 moves ( n ɨ 1) + 1
