Chapter 13

[Skip Breadcrumb Navigation]

Home

Student Resources

Quizzes

Chapter 13

Recursion

This activity contains 10 questions.

We have n people in a room, where n is an integer greater than or equal to 2. Each person shakes hands once with every other person.

Which of the following recursive functions correctly computes the total number of handshakes for n people in a room?

To get you started, if there are only one or two people in the room, then:

handshake(1) = 0
handshake(2) = 1

If a third person enters the room, she must shake hands with each of the two persons already there. Add these two handshakes to the previous number of handshakes and we get:

handshake(3) = handshake(2) + 2

int handshake(int n)
{
  int i,h=0;
  if (n==1) return 0;
  else if (n==2) return 1;
  else {
     for (i=0; i<n; i++) {
         h = (n-1) + handshake(n-1);
     }
     return h;
  }
}

int handshake(int n)
{
  if (n<2) return 0;
  else return ((n-1) + handshake(n-1));
}

int handshake(int n)
{
  return ((n-1) + handshake(n-1));
}

int handshake(int n)
{
  if (n==1) return 0;
  else if (n==2) return 1;
  else return (handshake(n-1));
}

In a recursive function such as:


void writeVertical(int n)
{
	int num;

	if (n<10) {
		cout << n << endl;
	}
	else {
		num = n % 10;
		writeVertical( n / 10);
		cout << num << endl;
	}
}

Each recursive call to writeVertical produces a new local variable "num". What mechanism makes this possible?

Virtual memory allows each num variable to be tracked separately.The num variable in each recursive call really refers to the same location in memory. It is simply overwritten with new values each time the function is invoked.Each num variable is allocated a new value from the heap and is returned to the heap when the variable goes out of scope.Local variables are created on the stack. Each recursive call pushes a new variable for "num" on the stack, so each "num" variable is kept separate.

Why does a recursive function with an incorrect base case result in a stack overflow error message?

Recursive calls use physical memory. Eventually all physical memory is exhausted and the program will crash.Each recursive call saves the state of the program on the stack (e.g., the return instruction, local variables, parameters). If the recursion never ends, eventually the stack will become full.C++ has a built-in parameter that limits the number of times a recursive function can be executed. If this limit is exceeded then C++ will stop and output an error message.The recursive function must not be splitting the problem up into smaller versions of the same task.

The following are two functions for computing the nth Fibonacci number, where Fib(0) = 1, Fib(1) = 1, and Fib(n) = Fib(n-1) + Fib(n-2) when n >= 2.


int recursiveFib(int n)
{
	if (n<0) return 0;
	else if (n==0) return 1;
	else if (n==1) return 1;
	else {
		return recursiveFib(n-1) + 
			   recursiveFib(n-2);
	}
}

int iterativeFib(int n)
{
	int last, secToLast, cur, i;

	if (n<0) return 0;
	else if (n==0) return 1;
	else if (n==1) return 1;
	else {	
		last = 1;
		secToLast = 1;
		cur = 2;
		for (i=2; i<=n; i++) {
			cur = last + secToLast;
			secToLast = last;
			last = cur;
		}
		return cur;
	}
}

What will be the performance difference between the two functions?

The recursive solution will run faster due to its simpler code and use of the stack.They will run about the same.The iterative version will run slightly faster because there is no overhead of making the recursive calls.The iterative version will run significantly faster because it uses a single loop that runs in time proportional to n.

Given the following recursive function for factorial, how would this be invoked to correctly compute the factorial for number n?


long factorial(long n, long current_solution)
{
	if (n==1) return current_solution;
	current_solution = n * current_solution;
	return (factorial(n-1, current_solution));
}

long n = 6;
cout << factorial(n, n);

long n = 6;
cout << factorial(l, 0);

No parameter values for the function will correctly compute the factorial.

long n = 6;
cout << factorial(n, 1);

What will the following function output when given the input of "neat!" ?


void MysteryFunction()
{
  char c;
  cin >> c;
  if (c!='!') MysteryFunction();
  cout << c;
  return;
}

neat!neattaen!taen

Which of the following functions recursively sums all numbers in the array?

int recursiveSum(int a[], int curIndex, 
          int numElements)
{
	if (curIndex==numElements) return 0;
	return (a[curIndex] + 
                recursiveSum(a,curIndex,numElements-1));
}

int main()
{
	int a[]={1,2,3,4};
	cout << recursiveSum(a,0,4) << endl;
	return 0;
}

int recursiveSum(int a[], int curIndex, 
          int numElements)
{
	if (curIndex==numElements-1) return 0;
	return (a[curIndex] + 
                recursiveSum(a,curIndex+1,numElements));
}

int main()
{
	int a[]={1,2,3,4};
	cout << recursiveSum(a,0,4) << endl;
	return 0;
}

int recursiveSum(int a[], int curIndex, 
          int numElements)
{
	if (curIndex==numElements) return 0;
	return (a[curIndex] + 
                recursiveSum(a,curIndex+1,numElements));
}

int main()
{
	int a[]={1,2,3,4};
	cout << recursiveSum(a,0,4) << endl;
	return 0;
}

int recursiveSum(int a[], int curIndex, 
          int numElements)
{
	if (curIndex==numElements) return 0;
	return (a[curIndex] + 
                recursiveSum(a,curIndex+1,
                     numElements-1));
}

int main()
{
	int a[]={1,2,3,4};
	cout << recursiveSum(a,0,4) << endl;
	return 0;
}

Which of the following functions recursively determines if the input string is a palindrome?

bool isPalindrome(string s, int leftIndex, 
            int rightIndex)
{
	if (leftIndex == rightIndex) return true;
	if (s[leftIndex]!=s[rightIndex]) return false;
	return (
               isPalindrome(s,leftIndex+1,rightIndex-1));
}

int main()
{
	string s = "rotor";
	cout << isPalindrome(s,0,s.length()-1) << endl;
	return 0;
}

bool isPalindrome(string s, int leftIndex, 
            int rightIndex)
{
	while (leftIndex<rightIndex) {
		if (s[leftIndex] != s[rightIndex]) 
			return false;
		leftIndex++;
		rightIndex--;
	}
	return true;
}

int main()
{
	string s = "rotor";
	cout << isPalindrome(s,0,s.length()-1) << endl;
	return 0;
}

bool isPalindrome(string s, int leftIndex, 
            int rightIndex)
{
	if (leftIndex < rightIndex) return true;
	if (s[leftIndex]!=s[rightIndex]) return false;
	return (
               isPalindrome(s,leftIndex+1,rightIndex-1));
}

int main()
{
	string s = "rotor";
	cout << isPalindrome(s,0,s.length()-1) << endl;
	return 0;
}

bool isPalindrome(string s, int leftIndex, 
            int rightIndex)
{
	if (leftIndex >= rightIndex) return true;
	if (s[leftIndex]!=s[rightIndex]) return false;
	return (
               isPalindrome(s,leftIndex+1,rightIndex-1));
}

int main()
{
	string s = "rotor";
	cout << isPalindrome(s,0,s.length()-1) << endl;
	return 0;
}

What will the following program output?


// Prototypes
void DoSomething(int arr[], int target, int &arrLength);
void DoSomething2(int arr[], int current, int target, int &arrLength);
void DoSomething3(int arr[], int target, int &arrLength);

// Function implementation
void DoSomething(int arr[], int target, int &arrLength)
{
	int i=0;
	DoSomething2(arr, i, target, arrLength);
}

void DoSomething2(int arr[], int current, int target, int &arrLength)
{
	if (current == arrLength) return;
	if (arr[current] == target) {
		DoSomething3(arr, current, arrLength);
		arrLength--;
	}
	else {
		DoSomething2(arr, current+1, target, arrLength);
	}
}

void DoSomething3(int arr[], int current, int &arrLength)
{
	if (current>=arrLength-1) return;
	arr[current] = arr[current+1];
	DoSomething3(arr, current+1, arrLength);
}

int main()
{
	int arr[] = {15, 3, 21, 7, 55};
	int arrLength = 5;

	DoSomething(arr, 3, arrLength);
	for (int i=0; i< arrLength; i++) {
		cout << arr[i] << ", ";
	}
	cout << endl;
	return 0;
}

15, 21, 7, 5515, 3, 21, 7, 5515, 21, 7, 55, 5515, 3, 7, 55

What will the following code output?


// Prototypes
void DoSomething(int arr[], int arrLength);
void DoSomething2(int arr[], int current, int arrLength);

// Function implementation
void DoSomething(int arr[], int arrLength)
{
	int i=0;
	DoSomething2(arr, i, arrLength);
}

void DoSomething2(int arr[], int currentIndex, int arrLength)
{
	int temp;
	
	if (currentIndex >= arrLength-1) return;
	DoSomething2(arr, currentIndex+1, arrLength-1);
	temp = arr[currentIndex];
	arr[currentIndex] = arr[arrLength-1];
	arr[arrLength-1] = temp;
}

int main()
{
	int arr[] = {15, 3, 21, 7,4, 55};
	int arrLength = 6;

	DoSomething(arr, arrLength);
	for (int i=0; i< arrLength; i++) {
		cout << arr[i] << ", ";
	}
	cout << endl;
	return 0;
}

3, 4, 7, 15, 21, 554, 7, 3, 21, 15, 5555, 4, 7, 21, 3, 1515, 3, 21, 7,4, 55

The Submit Answers for Grading feature requires scripting to function. Your browser either does not support scripting or you have turned scripting off.

So, the Submit Answers for Grading button below will not work.

The following Submit Answers for Grading button is provided in its place and will clear your answers:
The Clear Answers and Start Over feature requires scripting to function. Your browser either does not support scripting or you have turned scripting off.

So, the Clear Answers and Start Over button below will not work.

The following Clear Answers button is provided in its place and will clear your answers:

Your browser either does not support scripting or you have turned scripting off. Because of this, the answer choices will NOT appear in a different order each time the page is loaded, though that is mentioned below. Note that you do not need this feature to use this site.

Answer choices in this exercise appear in a different order each time the page is loaded.

Chapter 13

Why does a recursive function with an incorrect base case result in a stack overflow error message?

What will the following function output when given the input of "neat!" ? void MysteryFunction() { char c; cin >> c; if (c!='!') MysteryFunction(); cout << c; return; }

Which of the following functions recursively sums all numbers in the array?

Which of the following functions recursively determines if the input string is a palindrome?

What will the following function output when given the input of "neat!" ?
void MysteryFunction() { char c; cin >> c; if (c!='!') MysteryFunction(); cout << c; return; }