Previous Section
 < Free Open Study > 
Next Section


Exercises

  1. Explain what is meant by the following:

    1. base case

    2. general (or recursive) case

    3. run-time stack

    4. binding time

    5. tail recursion

  2. True or false? If false, correct the statement. Recursive functions:

    1. often have fewer local variables than the equivalent nonrecursive routines.

    2. generally use while or for statements as their main control structure.

    3. are possible only in languages with static storage allocation.

    4. should be used whenever execution speed is critical.

    5. are always shorter and clearer than the equivalent nonrecursive routines.

    6. must always contain a path that does not contain a recursive call.

    7. are always less "efficient," in terms of Big-O complexity.

  3. Use the Three-Question Method to verify the ValueInList function described in this chapter.

  4. Describe the Three-Question Method of verifying recursive routines in relation to an inductive proof.

  5. Which data structure would you most likely see in a nonrecursive implementation of a recursive algorithm?

  6. Using the recursive function RevPrint as a model, write the recursive function PrintList, which traverses the elements in the list in forward order. Does one of these routines constitute a better use of recursion? If so, which one?

Use the following function in answering Exercises 7 and 8:

int Puzzle(int base, int limit)
{
  if (base > limit)
    return -1;
  else
    if (base == limit)
      return 1;
    else
      return base*Puzzle(base+1, limit);
}

  1. Identify the following:

    1. the base case(s) of the function Puzzle

    2. the general case(s) of the function Puzzle

  2. Show what would be written by the following calls to the recursive function Puzzle:

    1. cout << Puzzle(14, 10);

    2. cout << Puzzle(4, 7);

    3. cout << Puzzle(0, 0);

  3. Given the following function:

    int Func(int num)
    {
      if (num == 0)
        return 0;
      else
        return num + Fun(num + 1);
    }
    
    1. Is there a constraint on the values that can be passed as a parameter for this function to pass the smaller-caller test?

    2. Is Func(7) a good call? If so, what is returned from the function?

    3. Is Func(0) a good call? If so, what is returned from the function?

    4. Is Func(-5) a good call? If so, what is returned from the function?

  4. Put comments on the following routines to identify the base and general cases and explain what each routine does.

    1. int Power(int base, int exponent)
      {
        if (exponent == 0)
          return 1;
        else
          return base * Power(base, exponent-1);
      }
      
    2. int Factorial(int number)
      {
        if (num > 0)
          return num * Factorial(num - 1);
        else
          if (num == 0)
            return 1;
      }
      
      
    3. void Sort(int values[], int fromIndex, int toIndex)
      {
        int maxIndex;
      
        if (fromIndex != toIndex)
        {
          maxIndex = MaxPosition(values, fromIndex, toIndex);
          Swap(values[maxIndex], values[toIndex]);
          Sort(values, fromIndex, toIndex - 1):
        }
      }
      
    1. Fill in the blanks to complete the following recursive function:

      int Sum(int info[], int fromIndex, int toIndex)
      // Computes   the sum of the items between fromIndex and toIndex.
      {
        if (fromIndex__________ toIndex)
          return _____________________;
        else
          return _____________________;
      }
      
    2. Which is the base case and which is the general case?

    3. Show how you would call this function to sum all the elements in an array called numbers, which contains elements indexed from 0 to MAX_ITEMS - 1.

    4. What run-time problem might you experience with this function as it is now coded?

  5. You must assign the grades for a programming class. The class is studying recursion, and students have been given this simple assignment: Write a recursive function SumSquares that takes a pointer to a linked list of integer elements and returns the sum of the squares of the elements.

    • Example:

      Click To expand

    SumSquares (listPtr) yields (5 * 5) + (2 * 2) + (3 * 3) + (1 * 1) = 39

    Assume that the list is not empty.

    You have received quite a variety of solutions. Grade the functions that follow, marking errors where you see them.

    1. int SumSquares(NodeType* list)
      {
        return 0;
        if (list != NULL)
          return (list->info*list->info) + SumSquares(list->next));
      }
      
    2. int SumSquares(NodeType* list) 
      {
        int sum = 0;
        while (list != NULL)
        {
          sum = list->info + sum;
          list = list->next;
        }
        return sum;
      }
      
    3. int SumSquares(NodeType* list)
      {
        if (list == NULL)
          return 0;
        else
          return list->info*list->info + SumSquares(list->next);
      }
      
    4. int SumSquares(NodeType* list)
      {
        if (list->next == NULL)
          return list->info*list->info;
        else
          return list->info*list->info + SumSquares(list->next);
      }
      
    5. int SumSquares(NodeType* list)
      {
        if (list == NULL)
          return 0;
        else
          return (SumSquares(list->next) * SumSquares(list->next));
      }
      
  6. The Fibonacci sequence is the series of integers

    0, 1, 1, 2, 3, 5, 8, 21, 34, 55, 89 ...
    
    

    See the pattern? Each element in the series is the sum of the preceding two items. There is a recursive formula for calculating the nth number of the sequence (the 0th number if Fib(0) = 0):

    1. Write a recursive version of the function Fibonacci.

    2. Write a nonrecursive version of the function Fibonacci.

    3. Write a driver to test the recursive and iterative versions of the function Fibonacci.

    4. Compare the recursive and iterative versions for efficiency. (Use words, not Big-O notation.)

    5. Can you think of a way to make the recursive version more efficient?

  7. The following defines a function that calculates an approximation of the square root of a number, starting with an approximate answer (approx), within the specified tolerance (tol).

    Click To expand
    1. What limitations must be made on the values of the parameters if this method is to work correctly?

    2. Write a recursive version of the function SqrRoot.

    3. Write a nonrecursive version of the function SqrRoot.

    4. Write a driver to test the recursive and iterative versions of the function SqrRoot.

  8. A sequential search member function of SortedType has the following prototype:

    void SortedType::Search(int value, bool& found);
    
    1. Write the function definition as a recursive search, assuming a linked list implementation.

    2. Write the function definition as a recursive search, assuming an array-based implementation.

  9. We want to count the number of possible paths to move from row 1, column 1 to row N, column N in a two-dimensional grid. Steps are restricted to going up or to the right, but not diagonally. The illustration that follows shows three of many paths, if N = 10:

    Click To expand
    1. The following function, NumPaths, is supposed to count the number of paths, but it has some problems. Debug the function.

      int NumPaths(int row, int col, int n)
      {
        if (row == n)
          return 1;
        else
          if (col == n)
            return NumPaths + 1;
          else
            return NumPaths(row + 1, col)   *   NumPaths(row, col + 1);
      }
      
    2. After you have corrected the function, trace the execution of NumPaths with n = 4 by hand. Why is this algorithm inefficient?

    3. You can improve the efficiency of this operation by keeping intermediate values of NumPaths in a two-dimensional array of integer values. This approach keeps the function from having to recalculate values that it has already figured out. Design and code a version of NumPaths that uses this approach.

    4. Show an invocation of the version of NumPaths you developed in part (c), including any array initialization necessary.

    5. How do the two versions of NumPaths compare in terms of time efficiency? Space efficiency?

  10. Given the following function:[3]

    int Ulam(int num)
    {
      if (num < 2)
        return 1;
      else
        if (num % 2 == 0)
          return Ulam(num / 2);
        else
          return Ulam (3 * num + 1);
    }
    
    1. What problems come up in verifying this function?

    2. How many recursive calls are made by the following initial calls:

      cout    << Ulam(7)  << endl;
      cout    << Ulam(8)  << end1;
      cout    << Ulam(15)  << end1;
      
  11. Explain the relationship between dynamic storage allocation and recursion.

  12. What do we mean by binding time, and what does it have to do with recursion?

  13. Given the following values in list:

    Click To expand

    Show the contents of the run-time stack during the execution of this call to BinarySearch:

    BinarySearch(info, 99, 0, 9);
    
  14. The parameter to the following two recursive routines is a pointer to a singly linked list of numbers, whose elements are unique (no duplicates) and unsorted. Each node in the list contains two members, info (a number) and next (a pointer to the next node).

    1. Write a recursive value-returning function, MinLoc, that receives a pointer to a list of unsorted numbers and returns a pointer to the node that contains the minimum value in the list.

    2. Write a recursive void function, Sort, that receives a pointer to an unsorted list of numbers and reorders the values in the list from smallest to largest. This function may call the recursive MinLoc function that you wrote in part (a). (Hint: It is easier to swap the values in the info part of the nodes than to reorder the nodes in the list.)

  15. True or false? If false, correct the statement. A recursive solution should be used when:

    1. computing time is critical.

    2. the nonrecursive solution would be longer and more difficult to write.

    3. computing space is critical.

    4. your instructor says to use recursion.

[3]One of our reviewers pointed out that the proof of termination of this algorithm is a celebrated open question in mathematics. See Programming Pearls by Jon Bentley for a discussion and further references.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)