CS274: Computer Architecture - Recursion in MIPS
Activity Goals
The goals of this activity are:- To properly use recursion and save the stack
- To diagram a call stack trace for a given program
The Activity
Directions
Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.Model 1: A Recursive Algorithm
Questions
- Draw a call stack for a call to
factorial(3). - What registers did
factorialsave to the stack, and why? In particular, why did it savera? - Remove
rafrom the stack and re-run this program. What happens, and why? - How might one implement the Fibonacci sequence?
Model 2: Key Formulas and Concepts Recap
A one-page summary of recursion in MIPS.
Key rules:
| Rule | Micro-example (factorial) |
|---|---|
A recursive procedure calls jal, and jal overwrites $ra -- so $ra MUST be saved to the stack in the prologue and restored in the epilogue. |
Without it, factorial returns to itself forever (or crashes) |
Save any argument you will still need after the recursive call, because $a0 gets overwritten too. |
Save n; after jal factorial returns (n-1)!, compute n × (n-1)! |
| Every recursion needs a base case that returns without another call. | if n <= 1, set $v0 = 1 and return |
| Each call gets its OWN stack frame; depth n recursion uses n frames of stack space. | factorial(3) stacks 3 frames of (saved $ra, saved n): 8 bytes each = 24 bytes |
Results flow back through $v0 as the frames unwind, last call first. |
1 → 2 × 1 = 2 → 3 × 2 = 6 |
The call stack for factorial(3) at its deepest moment (the stack grows downward; each frame saved $ra and its n):
higher addresses +---------------------------+ | main's frame | +---------------------------+ | factorial(3): $ra to main | | saved n = 3 | +---------------------------+ | factorial(2): $ra to fact | | saved n = 2 | +---------------------------+ | factorial(1): $ra to fact | | saved n = 1 | <- $sp (base case: returns v0 = 1) +---------------------------+ lower addresses unwinding: factorial(1) returns 1 -> factorial(2) computes 2*1 = 2 -> factorial(3) computes 3*2 = 6
The recursive skeleton, step by step:
- Prologue:
addi $sp, $sp, -8;sw $ra, 4($sp);sw $a0, 0($sp). - Base case test:
slti $t0, $a0, 2; if$t0= 1, set$v0= 1 and skip to the epilogue. - Recurse:
addi $a0, $a0, -1;jal factorial. - Combine: reload n with
lw $a0, 0($sp), then multiply it by$v0into$v0. - Epilogue:
lw $ra, 4($sp);addi $sp, $sp, 8;jr $ra.
Glossary:
| Term | One-line definition |
|---|---|
| Recursion | A procedure that calls itself on a smaller version of the problem. |
| Base case | The input for which the procedure answers directly, ending the chain of calls. |
| Call stack | The stack of frames for every call currently in progress, deepest call on top (lowest address). |
| Stack frame | One call's saved registers (at minimum $ra and needed arguments) on the stack. |
| Unwinding | The return phase: frames pop off and partial results combine into the final answer. |
| Stack overflow | Running out of stack memory, e.g. when a missing base case recurses forever. |
| Call stack trace (diagram) | A drawing of the frames on the stack at some instant, like the one above. |