Java Reference
In-Depth Information
2. Always start a recursive method with the base cases. Add the recursive calls after
that. If this rule is not followed, then the method may not terminate, that is, the
method may run forever (a.k.a., infinite recursion).
3. Avoid using recursion when possible. An iterative solution is usually faster and takes
less main memory.
4. There is a limitation to using a recursive method. Since the size of the stack grows
with every recursive call, it is easy to get a stack overflow error if there are too many
recursive calls.
5. Tail recursion is when there is a single recursive call that appears at the end of every
execution path. A recursive method that uses tail recursion can be easily rewritten
into a non-recursive method that uses an infinite
while
loop.
6. Dynamic programming creates a bottom-up solution. In contract, a recursion algo-
rithm represents the top-down approach. When applicable, dynamic programming can
be useful to avoid performing the same computations multiple times.
7. Bubble sort, insertion sort, and selection sort are easy to implement. However, they
are not very fast for big arrays. Quick sort can be fast in some cases, but it performs
poorly when the input array is close to being sorted. Conversely, merge sort has good
worst-case running time. Quick sort and merge sort cannot be easily implemented
without using recursion.
8. Binary search is very fast and it is a useful tool for locating an element in an array.
However, binary search only works when the array is sorted.
14.8 Exercises
1. Write a recursive method that computes the sum of the first 100 positive integers.
2. Write a recursive method takes as input an array and returns the smallest number in
the array. Add additional parameters to the method as needed.
3. Write a recursive method that takes as input an array. The method should reverse
the array. Add additional parameters to the method as needed.
4. Write a recursive method that computes the number of primes between the integers
a
and
b
. The method can call the
isPrime
method, which checks if a number is prime.
Identify if the original method uses tail recursion. If it does, then rewrite it as an
iterative method using an infinite
while
loop.
5. A palindrome is a string that reads the same forward and backward. Write a recursive
method that determines if the input string is a palindrome. Feel free to introduce
additional parameters to the method.
6. Write a recursive method that takes as input an integer and returns the binary rep-
resentation of the integer as a string. Feel free to introduce additional parameters to
the method and/or create more methods.
