Mastering Algorithms with C

Questions and Answers

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. ...