Intermediate Programming: Recursion

True/False
Indicate whether the statement is true or false.

____	1.	Recursive methods are always better than the equivalent iterative method.

____	2.	When a method returns, its activation record is moved to the bottom of the stack.

____	3.	Recursion can always be used in place of iteration and vice-versa.

Multiple Choice
Identify the choice that best completes the statement or answers the question.

____	4.	Functions that are defined in terms of themselves are called what?
a. | iterative | c. | looping
b. | recursive | d. | circular

____	5.	What type of error is produced when a program recurses infinitely and the computer runs out of memory?
a. | stack overflow error | c. | run-time error
b. | out of memory error | d. | Exception

____	6.	The linear search method has an execution time of:
a. | O(1) | c. | O(n)
b. | O(n^2) | d. | O(n^3)

____	7.	What is the maximum number of steps needed to binary search a list of 2^15 values?
a. | 15 | c. | 2^15
b. | 16 | d. | 6

____	8.	Which method of the Data class is used to find the current time?
a. | getDate() | c. | Time()
b. | getTime() | d. | Hour()

____	9.	What is the large storage area created at program startup called?
a. | memory | c. | call stack
b. | RAM | d. | program area

____	10.	About how long would it take to complete the Towers of Hanoi problem with 64 rings at the rate of 1 move per second?
a. | 600 years | c. | 600 minutes
b. | 600 million years | d. | 600 billion years

____	11.	Who many moves are required to complete the Towers of Hanoi problem for n rings.
a. | n^2 | c. | 2^n
b. | 2^n -1 | d. | 2^n-1

____	12.	What effect does doubling the amount of data do to the execution time of a method with complexity O(n)?
a. | doubles | c. | quadruples
b. | triples | d. | nothing

Completion
Complete each statement.

	13.	A recursive method must have a well-defined termination or __________ ___________.

	14.	the iterative version of the quicksort algorithm requires a data structure called a _______.

	15.	When a method is called, a(n) ___________ ___________ is added to the top of the call stack.

	16.	An algorithm is ____________ is no work is done in the algorithm after a recursive call.

Short Answer

	17.	What is the threshold where 10,000 + n^2 is faster than 10,000 + 200?