recursion on the stack
Recursion is a function that solves a problem by calling itself on a smaller version of the same problem, like a set of nested Russian dolls: open one and find another just like it inside, until you reach the tiny solid one at the center. Computing factorial(4) by saying it equals 4 times factorial(3), which equals 3 times factorial(2), and so on, is recursion. The natural question is: how can one function be running many times at once without its many copies of i and n getting tangled together?
The stack is the answer. Each call to the function builds its own fresh stack frame, with its own private copies of the arguments and locals, stacked below the frame of the call that made it. As the recursion descends, frames pile up; each one remembers its own return address and its own data. When the base case is finally reached (the doll that does not open), the calls return one by one, each frame is torn down, and control unwinds back up the stack, combining the results on the way out. The stack pointer descending and then climbing back up is the physical trace of going deeper and then returning.
Recursion on the stack matters because it shows the stack is not just bookkeeping; it is what gives each invocation its own world. It also reveals the cost: every level of depth consumes a frame, so unbounded recursion (a missing or wrong base case) keeps allocating frames until it runs past the reserved stack region, which is a stack overflow. This is why deep recursion can be dangerous where stack space is tight, and why some compilers turn a special case, tail recursion, into a plain loop that reuses one frame instead of growing the stack.
factorial(n): each call saves ra and n, recurses on n-1, then multiplies on the way back. fact: addi sp, sp, -16 sd ra, 8(sp) sd a0, 0(sp) # save my own n in my own frame li t0, 1 ble a0, t0, base # base case: n <= 1 addi a0, a0, -1 jal ra, fact # recurse: a new frame for fact(n-1) ld t1, 0(sp) # reload my n mul a0, a0, t1 # n * fact(n-1) j ret_ base: li a0, 1 ret_: ld ra, 8(sp) addi sp, sp, 16 ret
Each recursive call gets its own frame holding its own n and return address; the stack grows down and unwinds back up.
Recursion is not magic memory: every level costs a stack frame, so a missing base case overflows the stack. Tail recursion can sometimes be turned into a loop that reuses one frame.