What is Recursion?
Recursion is when a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. Think of it like Russian nesting dolls - each doll contains a smaller version of itself until you reach the smallest one. In programming, recursion continues until it reaches a 'base case' that stops the self-calling process.
Key Points:
- Recursion is a function calling itself
- Must have a base case to stop recursion
- Each call works on a smaller problem
- Useful for naturally recursive problems
Example Code
# Simple recursive countdown
# countdown(3) prints: 3, 2, 1, Blastoff!
countdown:
# Base case: if n == 0, stop
beq $a0, $zero, base_case
# Print current number
move $a0, $a0 # (syscall to print)
# Recursive case: countdown(n-1)
addi $a0, $a0, -1
jal countdown
jr $ra
base_case:
# Print "Blastoff!"
jr $ra