Introduction to Programming with C++, Third Edition, Y. Daniel Liang

This quiz is for students to practice. A large number of additional quiz is available for instructors using Quiz Generator from the Instructor's Resource Website. Videos for Java, Python, and C++ can be found at https://yongdanielliang.github.io/revelvideos.html.

Many questions in this edition have been updated in the new edition. Please check with the publisher on the newest edition.

Chapter 17 Recursion


Section 17.2 Example: Factorials
17.1  Which of the following statements are true?
A. Every recursive function must have a base case or a stopping condition.
B. Every recursive call reduces the original problem, bringing it increasingly closer to a base case until it becomes that case.
C. Infinite recursion can occur if recursion does not reduce the problem in a manner that allows it to eventually converge into the base case.
D. Every recursive function must have a return value.
E. A recursive function is invoked differently from a non-recursive function.

17.2  Fill in the code to complete the following function for computing factorial.

  /** Return the factorial for a specified index */
  long factorial(int n)
  {
    if (n == 0) // Base case
      return 1;
    else
      return _____________; // Recursive call
  }
A. n * (n - 1)
B. n
C. n * factorial(n - 1)
D. factorial(n - 1) * n

17.3  What are the base cases in the following recursive method?

void f(int n) 
{
  if (n > 0)
  {
    cout << n % 10;
    f(n / 10);
  }
} 
A. n > 0
B. n <= 0
C. no base cases
D. n < 0

17.4  Analyze the following recursive function.

  long factorial(int n)
  {
    return n * factorial(n - 1);
  }
A. Invoking factorial(0) returns 0.
B. Invoking factorial(1) returns 1.
C. Invoking factorial(2) returns 2.
D. Invoking factorial(3) returns 6.
E. The function runs infinitely and runs out of memory.

Section 17.3 Example: Fibonacci Numbers
17.5  Which of the following statements are true?
A. The Fibonacci series begins with 0 and 1, and each subsequent number is the sum of the preceding two numbers in the series.
B. The Fibonacci series begins with 1 and 1, and each subsequent number is the sum of the preceding two numbers in the series.
C. The Fibonacci series begins with 1 and 2, and each subsequent number is the sum of the preceding two numbers in the series.
D. The Fibonacci series begins with 2 and 3, and each subsequent number is the sum of the preceding two numbers in the series.

17.6  Fill in the code to complete the following function for computing a Fibonnaci number.

  long fib(long index)
  {
    if (index == 0) // Base case
      return 0;
    else if (index == 1) // Base case
      return 1;
    else // Reduction and recursive calls
      return __________________;
  }
A. fib(index - 1)
B. fib(index - 2)
C. fib(index - 1) + fib(index - 2)
D. fib(index - 2) + fib(index - 1)

Section 17.4 Problem Solving Using Recursion
17.7  In the following function, what is the base case?

int xFunction(int n) 
{
  if (n == 1)
    return 1;
  else
    return n + xFunction(n - 1);
}
A. n is 1.
B. n is greater than 1.
C. n is less than 1.
D. no base case.

17.8  What is the return value for xFunction(4) after calling the following function?

int xFunction(int n) 
{
  if (n == 1)
    return 1;
  else
    return n + xFunction(n - 1);
}
A. 12
B. 11
C. 10
D. 9

17.9  Fill in the code to complete the following function for checking whether a string is a palindrome.

bool isPalindrome(const char * const s)
{
  if (strlen(s) <= 1) // Base case
    return true;
  else if _____________________________ // Base case
    return false;
  else
    return isPalindrome(substring(s, 1, strlen(s) - 2));
}
A. (s[0] != s[strlen(s) - 1])
B. (s[0] == s[strlen(s) - 1])
C. (s[0] <> s[strlen(s) - 1])
D. (s[0] = s[strlen(s) - 1])

17.10  Analyze the following code:

  #include <iostream>
  using namespace std;

  void xFunction(int x[], int length)
  {
    cout << " " << x[length - 1];
    xFunction(x, length - 1);
  }
  
  int main()
  {
    int x[] = {1, 2, 3, 4, 5};
    xFunction(x, 5);
  }
A. The program displays 1 2 3 4 6.
B. The program displays 1 2 3 4 5 and then raises an ArrayIndexOutOfBoundsException.
C. The program displays 5 4 3 2 1.
D. The program displays 5 4 3 2 1 and then raises an ArrayIndexOutOfBoundsException.

Section 17.5 Recursive Helper Functions
17.11  Fill in the code to complete the following function for checking whether a string is a palindrome.

bool isPalindrome(const char * const s, int low, int high)
{
  if (high <= low) // Base case
    return true;
  else if (s[low] != s[high]) // Base case
    return false;
  else
    return ____________________________;
}

bool isPalindrome(const char * const s)
{
  return isPalindrome(s, 0, strlen(s) - 1);
}
A. isPalindrome(s)
B. isPalindrome(s, low, high)
C. isPalindrome(s, low + 1, high)
D. isPalindrome(s, low, high - 1)
E. isPalindrome(s, low + 1, high - 1)

17.12  Fill in the code to complete the following function for sorting a list.

void sort(char list[], int high)
{
  if (high > 1)
  {
    // Find the largest element and its index
    int indexOfMax = 0;
    char max = list[0];
    for (int i = 1; i <= high; i++)
    {
      if (list[i] > max)
      {
        max = list[i];
        indexOfMax = i;
      }
    }

    // Swap the largest with the last element in the list
    list[indexOfMax] = list[high];
    list[high] = max;

    // Sort the remaining list
    sort(list, high - 1);
  }
}

void sort(char list[])
{
  ____________________________;
}


void sort(double[] list) {
  ___________________________;
}
A. sort(list)
B. sort(list, strlen(list))
C. sort(list, strlen(list) - 1)
D. sort(list, strlen(list) - 2)

17.13  Fill in the code to complete the following function for binary search.

int binarySearch(const int list[], int key, int low, int high)
{
  if (low > high) // The list has been exhausted without a match
    return -low - 1; // Return -insertion point - 1

  int mid = (low + high) / 2;
  if (key < list[mid])
    return binarySearch(list, key, low, mid - 1);
  else if (key == list[mid])
    return mid;
  else
    return binarySearch(list, key, mid + 1, high);
}

int binarySearch(const int list[], int key, int size)
{
  int low = 0;
  int high = size - 1;
  return __________________________;
}
A. binarySearch(list, key)
B. binarySearch(list, key, low + 1, high - 1)
C. binarySearch(list, key, low - 1, high + 1)
D. binarySearch(list, key, low, high)

Section 17.6 Tower of Hanoi
17.14  How many times the recursive moveDisks function is invoked for 3 disks?
A. 3
B. 7
C. 10
D. 14

17.15  How many times the recursive moveDisks function is invoked for 4 disks?
A. 5
B. 10
C. 15
D. 20

17.16  Analyze the following two programs:

A:

  void xFunction(int length)
  {
    if (length > 1)
    {
      cout << (length - 1) << " ";
      xFunction(length - 1);
    }
  }

  int main()
  {
    xFunction(5);
  }

B:
  public static void xFunction(int length)
  {
    while (length > 1)
    {
      cout << (length - 1) << " ";
      xFunction(length - 1);
    }
  }

  int main()
  {
    xFunction(5);
  }
A. The two programs produce the same output 5 4 3 2 1.
B. The two programs produce the same output 1 2 3 4 5.
C. The two programs produce the same output 4 3 2 1.
D. The two programs produce the same output 1 2 3 4.
E. Program A produces the output 4 3 2 1 and Program B prints 4 3 2 1 1 1 .... 1 infinitely.

Section 17.7 Recursion versus Iteration
17.17  Which of the following statements are true?
A. Recursive functions run faster than non-recursive functions.
B. Recursive functions usually takes more memory space than non-recursive functions.
C. A recursive function can always be replaced by a non-recursive function.
D. In some cases, however, using recursion enables you to give a natural, straightforward, simple solution to a program that would otherwise be difficult to solve.