Previous Section
 < Free Open Study > 
Next Section


Chapter 7

    1. The base case is a nonrecursive exit from the recursive routine.

    2. The general (or recursive) case is a path that includes a recursive call to the routine, to solve a smaller version of the original problem.

    3. The run-time stack is a structure that keeps track of the activation records at run time, so as to preserve the values of parameters, return addresses, registers, and so on.

    4. Binding time refers to the point in the compile/execution cycle when variable names are associated with addresses in memory.

    5. Tail recursion occurs when the recursive call is the last statement executed in a recursive function.

    1. True

    2. False

    3. False

    4. False

    5. False. Recursive routines are often shorter and clearer but not always.

    6. True

    7. False. Recursive routines are often the same as the nonrecursive solution, in terms of Big-O notation.

    1. Base Case: One base case occurs when the value is found on this call and the function exits without any further calls to itself. A second base case occurs when the end of the list is reached without the value being found and the function exits without any further recursive calls. The answer is yes.

    2. Smaller Caller: The recursive call in the general case increments the value of start-Index, making the part of the list left to be searched smaller. The answer is yes.

    3. General Case: Assume that the recursive call in the general case correctly tells us whether the value is found in the second through last elements in the list. Then base case 1 gives the correct answer of true if the value is found in the first element in the list, base case 2 gives the correct answer of false if the value is not in the first element and the first element is the only element in the list. The only other possible case is that the value exists somewhere in the rest of the list. Assuming that the general case works correctly, the entire function works, so the answer to this question is also yes.

    1. -1

    2. 120

    3. 1

    1. Yes, num must be zero or a negative number.

    2. No.

    3. Yes. 0 is returned.

    4. Yes. -15 is returned

    1. This answer is incorrect. The value 0 is returned; the recursive case is never reached. This solution gets half credit, because it correctly calculates the base case (even if it doesn't reach it).

    2. This solution correctly calculates the sum of squares but gets no credit because it is not a recursive solution.

    3. This answer is correct and gets full credit.

    4. This answer is functionally equivalent to (c); it just avoids the last recursive call (to an empty list) by returning the sum of the last squares as the base case. This answer runs into problems if the list is empty, but the specification states that the list is not empty. This answer gets full credit.

    5. This solution is incorrect. The general case does not correctly calculate the sum of the squares. Quarter credit is given for using the correct control structure and for getting the base case correct.

    1. int Fibonacci(int number)
      {
        if (number <= 1)
          return number;
        else
          return Fibonacci(number - 2) + Fibonacci(number - 1);
      }
      
    2. int Fibonacci(int number)
      {
        int current;
        int previous;
        int temp;
      
      
        if (number <= 1)
          return 1;
        else
        {
          previous = 0;
          current = 1;
          for (int count = 2; count <= number; count++)
          {
            temp = previous;
            previous = current;
            current = temp + previous;
          }
          return current;
        }
      }
      
    3. #include <iostream>
      int Fibonacci(int number);
      int main()
      {
        using namespace std;
        int number:
        cout << "Input the Fibonacci number you wish." << end1;
           << "Input a negative number to quit."  << end1;
        cin >> number;
        while (number >= 0)
        {
          cout  << "number: "  << number  << end1;
              << "Fibonacci number: "  << Fibonacci(number)  << end1;
          cout << "Input the Fibonacci number you wish." << end1;
             << "Input a negative number to quit."  << end1;
          cin  >> number;
        }
        return 0;
      }
      // Put the function version you are testing here.
      
    4. The recursive solution is inefficient because some of the intermediate values are calculated more than once.

    5. The following version, which uses an auxiliary recursive function, is more efficient. The recursive parameters keep track of the current and previous numbers, rather than recalculating them.

      int Fibonacci(int number)
      {
        return Fib(number, 1, 1);
      }
      int Fib(int number, int previous, int current)
      {
        if (number == 0)
          return previous;
        else
          return Fib(number - 1, current, current + previous)
      }
      
    1. It is difficult to establish that the recursive calls satisfy Question 2, that they are moving toward the base case.

    2. std: :cout << Ulam (7) << end1; 16 recursive calls

      std::cout << Ulam (8) << end1; 3 recursive calls

      std::cout << Ulam (15) << end1; 17 recursive calls

    1. NodeType* MinLoc(NodeType* list, NodeType*& minPtr)
      {
        if (list != NULL
        {
          if (list->info < minPtr->info)
            minPtr = list;
          return MinLoc(list->next, minPtr);
        }
        else
          return minPtr;
      }
      
    2. void Sort(NodeType* list);
      {
        NodeType* minPtr;
        int temp;
      
        if (list != NULL)
        {
          minPtr = MinLoc(list, list);  // Swap
          temp = minPtr->info;
          minPtr->info = list->info;
          list->info = temp;
          Sort (list->next);            // Sort rest of list
        }
      }
      
    1. False. Recursive solutions are often less efficient in terms of computing time.

    2. True

    3. False. Recursive solutions generally require more space in the run-time stack.

    4. True. (Don't you want a good grade in this course?)



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