Given a stack of integers and a value val, insert val at the very bottom of the stack, preserving the relative order of everything already there — using only the standard stack operations (push, pop, top, isEmpty), with no other explicit data structure to hold values in transit. Recursion turns out to be exactly the tool for this: popping the top element and holding it as a local variable in the current recursive call is functionally identical to pushing it onto an auxiliary stack — except the "stack" being used is the program's own call stack, never declared explicitly anywhere in the code. Recursing all the way down to an empty stack (the base case) is where the new value actually gets pushed; as the recursion unwinds, each call restores its own held-aside value on top, rebuilding the original order above the new bottom.