Question

QUESTION 1

For the following recursive function, find f(5):

int f(int n)
{
if (n == 0)
   return 0;
else
   return n * f(n - 1);
}

	A.	120
	B.	60
	C.	1
	D.	0

10 points   

QUESTION 2

Which of the following statements could describe the general (recursive) case of a recursive algorithm?

In the following recursive function, which line(s) represent the general (recursive) case?

void PrintIt(int n ) // line 1

{ // line 2

if (n > 0) //line 3

{ //line4

cout << "Again" << endl; //line 5

PrintIt(n - 1); // line 6

} // line 7

else // line 8

cout << n << endl; // line 9

} // line 10

	A.	Lines 5 6
	B.	Lines 5 9
	C.	Lines 6 9
	D.	Line
	E.	None of the above.

10 points   

QUESTION 3

Recursion is memory-intensive because:

	A.	Recursive functions tend to declare many local variables.
	B.	Many copies of the function code are created
	C.	Previous function calls are still open when the function calls itself and the activation records of these previous calls still occupy space on the call stack.
	D.	It requires large data values
	E.	None of these answers are correct.

10 points   

QUESTION 4

Recursion uses more memory space than iteration because

	A.	it uses stack instead of queue.
	B.	every recursive call has to be stored.
	C.	both A & B are true.
	D.	None of the above are true.

10 points   

QUESTION 5

Read the following code and determine what goes in blank #1.

int Length(NodeType* list)

// Pre: list has been initialized.

// Post: Length returns the number of elements in list. No counter is kept as

// part of the list. This function is recursive.

{

if (______________) // 1

_______________; // 2

else _______ // 3

}

	A.	list == NULL
	B.	list->info = 0
	C.	list->next == NULL
	D.	list != NULL
	E.	None of these answers is correct.

Answer 1

Answers:

(1). You can trace the output by performing the execution as follows:

f(5) = 5 * f(5-1) // because n=5 is not = 0 so it goes in else part

So, f(5) = 5 * f(4)
= 5 * 4 * f(3) // because n=4 is non-zero so again in else part
= 5 * 4 * 3 * f(2)
= 5 * 4 * 3 * 2 * f(1)
= 5 * 4 * 3 * 2 * 1 * f(0)
= 5 * 4 * 3 * 2 * 1 * 0 // for n=0, f() returns 0
= 0

So, the answer is (D) 0.

(2). The recursive case / general case can easily be fond by looking in the function code. Recursion means the function is calling itself. So, search for the name of function PrintIt() in its code, it is at line 6. So, this is the answer, as it is not an option, you can consider line 5 and combine it because it only prints that now we are going to do recursion. So, the answer is (A) Lines 5 6.

(3). The correct option is (C).

The reason behind this is, when a function call is made, the return address is stored first in the stack, then the control is transferred to the called function, then after finishing the execution, again control goes to the calling function. So, for every function call in the recursion, it needs to store in the stack. So, correct option is Option (C) because it needs more memory and it is memory intensive.

(4). The answer is (B).

There is no concept of using queue for iteration. So, the option (a) is not possible. As I wrote in the question (3), every recursive call need to be stored in stack along with the return address to execute the sentence perfectly. So, option (B) is correct.

(5). The answer is (A) list == NULL.

This is also a recursive function and in the recursive function, see the question (1). In the if condition, we are writing the condition when the recursion is needed to stop the execution. The recursive part comes in the else statement.

The given function is to find the length of the list. So, in the if part we check whether the node is NULL then we need to stop the execution otherwise we go one level down and find the total number of levels for that node in the else part. So, the if part checks whether the list pointer is NULL. So, the answer (A) is correct for this question.

Please comment if there is any query. Thank you. :)