**Q:** The following recursive
definition has an error. What is it, and how can we fix it? For a
positive integer *n*, the definition, in its proper
form, is common in formally computing the running time of
divide-and-conquer algorithms, such as merge sort (see Chapter 12). Merge sort divides a set
of data in half, then divides the halves in half, and continues this
way until each division contains a single element. Then, during the
unwinding phase, the divisions are merged to produce a final sorted
set.

**A:** The problem with this
definition is that it never reaches the terminating
condition, *n* = 0, for any initial value of
*n* greater than 0. To fix the problem, it needs an
obtainable terminating condition. The condition *n*
= 1 works well, which means we should also change the second condition
in the function. A recursive definition with an acceptable terminating
condition is presented here:

This happens to be the correct definition for the running time
of merge sort. Such a function is called a
*recurrence*. In more formal analysis, recurrences are used frequently
to describe the running times of recursive algorithms.

**Q:** Describe a recursive approach for computing the prime factors of a number. Determine whether the approach is tail recursive, and describe why or why not. ...

Start Free Trial

No credit card required