the stack and recursion

Why is the stack the data structure behind recursion? Because recursion and a stack share the same shape: the thing started most recently must finish first. When function f calls g, which calls h, you cannot return from f until g has returned, and you cannot return from g until h has returned. That last-in-first-out discipline is exactly what a stack enforces — so the machinery that tracks pending calls is literally called the call stack.

Here is the mechanism in plain steps. Each time a program enters a function, it pushes a frame onto the call stack holding the return address and the function's local variables. Each time a function returns, that frame is popped, restoring the caller's state. Because pushes and pops always touch the top, the most deeply nested call is always the one currently being worked on, and the chain unwinds in perfect reverse order. The same idea evaluates arithmetic expressions: to compute (3 + 4) * 5 you push partial results and operators, and pop them as you resolve each parenthesised piece — nested structure handled by a stack.

This is the concrete, everyday face of the whole field. A pushdown automaton is a finite control plus a stack precisely because nested, recursive structure — balanced brackets, nested blocks, recursive grammar rules — is what a single stack can track and a finite memory cannot. When a compiler parses a recursively defined grammar by recursive descent, the program's own call stack IS the PDA's stack. So the abstract theory and the runtime behaviour of real programs are two views of the same machine: a finite controller backed by a last-in-first-out memory.