ITPEC FE Morning October 2020 Question 9

Recursive stack transfer — trace a recursive function that moves elements between three stacks.

Given stacks A = [1,2,3], B = [1,2,3], C = [1,2,3] (top = rightmost), function f():
- Pops from A → pushes to C (recursive descent)
- Pops from C → pushes to B (recursive return)

Trace:

• •Descent phase (A→C): pop 3, 2, 1 from A, push onto C
• •C becomes [1,2,3,3,2,1]
• •Return phase (C→B): pop 1, 2, 3 from C, push onto B
• •B becomes [1,2,3,1,2,3]

Answer: (a) [1, 2, 3, 1, 2, 3]

Why not others:
- (b) [1,2,3,3,2,1] — would require pushing in reverse (no re-reversal on return)
- (c) [3,2,1,1,2,3] — wrong order of original elements
- (d) [3,2,1,3,2,1] — would require popping from bottom of stack

Key rule: Double reversal through a temporary stack restores original order. The recursive structure acts like two reversals: A→C reverses, C→B reverses again.

AI-generated — may contain errors