Knowledge
Comprehension
Application
Analysis
Evaluation
100
The type of recursion in which the recursive call is done before a series of operations
What is non-tail recursion?
100
int mystery(int n) { if (n==1) return 1; else return n*mystery(n-1); }
What is factorial?
100
int infinite() { _(); }
What is infinite?
100
A recursive log2(int n) function requires O(_) additional space complexity.
What is O(log(n))?
100
int sum(int n) { (n==0) ? 0 : n+sum(n); }
What is sum(n-1)?
200
The two types of cases in a recursive function definition
What are base and recursive?
200
A return corresponds to a _ of the function stack
What is pop?
200
int trace(int **A, int n) { if (n==_) return _; else return A[n-1] + trace(A, n-2); }
What are -1 and 0?
200
A recursive int fib(int n) function requires _ time complexity
What is exponential?
200
int fib(int n) { return (n<=2) ? (fib(n-1)+fib(n-2)) : 1; }
What is 1 : (fib(n-1)+fib(n-2))?
300
The construct used to keep track of recursive calls and their parameters
What is the function stack?
300
int mystery(int a, int n) { return (a==1) ? a : a*mystery(a, n-1); }
What is exponentiation?
300
If I switch the order of the _ and _ cases in a recursive two-liner, I get _ recursion
What are base, recursive, and infinite?
300
How many times is the number 1 returned by a call to fib(6)?
What is 8?
300
Fix two words in the following poem: To reverse a string, Put the first thing first, Put the last thing last, And between, the reverse Of the rest of the thing.
What is first -> last, last -> first?
400
If a recursive function has no base case it recurses _
What is infinitely
400
int Node::_() { if (!node->next) return 1; else return 1+node->next->_(); }
What is size?
400
void Tree::_() { std::swap(left, right)? left->_(); right->(); }
What is reverse?
400
If a tree holds n nodes, how many traversals does it take to find a key?
What is log(n)?
400
Correct exactly one word in the following to make it true To *print* a string backwards, I *print* the substring containing all but the first character, and then output the last character
What is last->first?
500
The two most popular O(nlog(n)) sorting algorithms which use recursion
What are mergesort and quicksort?
500
float _(int n) { if (n==1) return 1; else return 1/(1+_()); }
What is golden ratio?
500
What is y(15)? int y(int x) { if (!x) return x; else return x+y(x/2); }
What is 31?
500
If a balanced tree has height h, how many links does it have?
What is 2^h-2?
500
fib(INT_MAX);
What is stack overflow?
M
e
n
u