1 (???) (15 points)
a. Show a NEAT drawing of the resulting list when F(list) is executed and explain briefly what the function F does.

list

Node* & F(Node* &  list){
	if (list)   
		if (list->next){
			Node* p1 = list;
			Node* p2 = list->next;
			list = F(list->next);
			p2->next = p1;
			p1->next = NULL;
	}
	return list;  
}

b. Show the output generated by a call to G(5);

void G(int N){
	if (N > 0){
		cout << "starting G  " << N << endl;
		G(N-1);
		cout << "ending   G  "<< N << endl;
	}
}

void H(int N){
	if (N > 0){  
		cout << "starting H  " << N << endl;
		H(N-1);
		cout << "middle   H  " << N << endl;
		H(N-1);
		cout << "ending   H  " << N << endl;
	}
}

d. Show the output generated by the statement:

     cout << "J(2,2):  " << J(2,2) << endl;

int J(int N, int K){
// count is initialized at 1 and incremented by 1 in each call
	static int count = 1;
	cout << setw(8) << count++ << setw(8) << N << setw(8) << K << endl;
	if (N == 0) return 1;
	if (K == 0) return 1;
	return (J(N, K-1) + J(N-1, K));
}

e Show the output generated, in the 200x200 Drawing window, by the
statement:
Squares(100, 100, 200);

void Squares(int x, int y, int size){
	int half = size / 2;
	int quarter = size / 4;
	if (size > 10){ 
		FrameRect(x - half, y - half, x + half, y + half);
		Squares(x - quarter, y - quarter, half);
		Squares(x + quarter, y + quarter, half);
	}
}

2. (Writing Recursive Functions) (10 points)
a. Write a recursive C++ function to test whether a string is a palindrome.

b. Write a recursive C++ function to count the number of n-digit binary numbers that do NOT have two ones in a row.

For example, if n = 3, these sequences do not have two ones in a row:

000, 001, 010, 100, 101

and these sequences do have two ones in a row:

110, 011, 111.

Last Updated: April 15, 1997 10:54 am by