Chapter 22 Self-Assessment Quiz: Recursion
Test your understanding of recursion. Try to answer each question before revealing the answer.
Section 1: Multiple Choice
Q1. Every correct recursive function must have:
(a) At least two recursive calls (b) A base case and a recursive case (c) A global variable to track depth (d) A loop as a fallback
Answer
(b) Every recursive function needs a base case (to stop the recursion) and a recursive case (to make progress toward the base case). Not all recursive functions have multiple recursive calls — factorial has only one. No global variable or loop is required.Q2. What is the maximum number of stack frames alive simultaneously during a call to Factorial(10)?
(a) 10 (b) 11 (c) 55 (d) 3628800
Answer
(b) Factorial(10) calls Factorial(9), which calls Factorial(8), ..., down to Factorial(0). That is 11 frames: one for each value from 10 down to 0. The number 55 is the sum 1+2+...+10, and 3628800 is 10! — neither is the stack depth.Q3. The naive recursive Fibonacci has time complexity:
(a) O(n) (b) O(n log n) (c) O(n²) (d) O(2ⁿ)
Answer
(d) Each call spawns two more calls, creating an exponential tree of calls. The exact complexity is O(φⁿ) where φ ≈ 1.618 is the golden ratio, but O(2ⁿ) is the standard simplification.Q4. What does this function return for Mystery(4)?
function Mystery(N: Integer): Integer;
begin
if N <= 1 then
Mystery := 1
else
Mystery := Mystery(N - 1) + Mystery(N - 2);
end;
(a) 4 (b) 5 (c) 8 (d) 10
Answer
(b) This is the Fibonacci function with a different base case. Mystery(1)=1, Mystery(2)=Mystery(1)+Mystery(0)=1+1=2, Mystery(3)=Mystery(2)+Mystery(1)=2+1=3, Mystery(4)=Mystery(3)+Mystery(2)=3+2=5.Q5. Which traversal order prints a binary search tree's values in sorted order?
(a) Pre-order (b) In-order (c) Post-order (d) Level-order
Answer
(b) In-order traversal visits Left, then Node, then Right. For a binary search tree, all left descendants are smaller and all right descendants are larger, so in-order traversal produces values in ascending sorted order.Q6. A recursive function is "tail recursive" if:
(a) It has exactly one recursive call
(b) The recursive call is the first statement
(c) The recursive call is the last operation before returning
(d) It uses a while loop internally
Answer
(c) Tail recursion means the recursive call is the very last thing the function does — the function returns the result of the recursive call directly, without any additional computation (like multiplication or addition) after the call.Q7. What does Pascal's forward keyword enable?
(a) Tail call optimization (b) Mutual recursion between two functions (c) Recursion without a base case (d) Stack overflow protection
Answer
(b) Theforward keyword declares a function's signature before its body is defined, allowing another function to call it before its full definition appears. This is necessary for mutual recursion, where A calls B and B calls A.
Q8. Which of the following is the BEST reason to choose recursion over iteration?
(a) Recursion is always faster (b) The problem has naturally self-similar structure (c) Loops are harder to write (d) Recursion uses less memory
Answer
(b) Recursion is best when the problem itself is recursive — trees, nested structures, divide-and-conquer decompositions. Recursion is NOT always faster (often slower due to call overhead), loops are not inherently harder, and recursion typically uses MORE memory (stack frames).Section 2: True or False
Q9. True or False: Every recursive algorithm can be rewritten as an iterative one.
Answer
True. Any recursive algorithm can be converted to iteration using an explicit stack. The call stack in recursion is effectively an implicit stack; making it explicit converts recursion to iteration.Q10. True or False: A recursive function that makes two recursive calls (like Fibonacci) always has exponential time complexity.
Answer
False. Two recursive calls do not automatically mean exponential time. Merge sort makes two recursive calls but has O(n log n) complexity because the work at each level is O(n) and the depth is O(log n). The exponential complexity of naive Fibonacci comes from overlapping subproblems — the same values being recomputed many times — not merely from having two calls.Q11. True or False: If a recursive function has a correct base case, it cannot cause a stack overflow.
Answer
False. A correct base case prevents infinite recursion, but very deep recursion (e.g., processing a linked list of 100,000 nodes) can still overflow the stack even though it will eventually terminate. The issue is stack size, not correctness.Q12. True or False: In Pascal, each recursive call gets its own copy of the function's local variables.
Answer
True. Each recursive call creates a new stack frame with its own copies of local variables and value parameters. This is why Factorial(3) and Factorial(2) each have their own independent N.Section 3: Short Answer
Q13. Given the following recursive function, what is the output of PrintPattern(4)?
procedure PrintPattern(N: Integer);
var
I: Integer;
begin
if N > 0 then begin
PrintPattern(N - 1);
for I := 1 to N do
Write('*');
WriteLn;
end;
end;
Answer
* ** *** ****Because the recursive call comes before the print statement, the smallest value (1) prints first (during unwinding from the deepest call), building up to the largest value (4).
Q14. A student writes the following and claims it computes 2ⁿ. Is it correct? If not, what does it actually compute?
function Mystery(N: Integer): Integer;
begin
if N = 0 then
Mystery := 1
else
Mystery := Mystery(N - 1) + Mystery(N - 1);
end;
Answer
It IS correct — it computes 2^N. When N=0, returns 1 (=2^0). For N>0, it returns 2^(N-1) + 2^(N-1) = 2 * 2^(N-1) = 2^N. However, it is extremely inefficient — O(2^N) time complexity because it recomputes the same value twice at every level. A simpleMystery := 2 * Mystery(N - 1) would be O(N), and a loop would be even better.
Q15. Name two advantages of recursive tree traversal over iterative tree traversal, and two advantages of iterative tree traversal over recursive.