Architecture / ISA
Advanced
MIPS32 / MARS / QtSpim
MIPS 어셈블리 스택 프레임을 이용한 재귀 함수(피보나치) 구현
함수 호출 시 복귀 주소($ra)와 로컬 변수($s0)를 스택 메모리에 저장/복원하여 재귀 호출(Recursion)을 안정적으로 처리하는 MIPS 어셈블리 패턴.
#MIPS #Assembly #Recursion #Stack #Fibonacci
핵심 개념재귀 함수는 자기 자신을 다시 호출(
jal)하므로, 호출 직전의 복귀 주소($ra)가 덮어써지지 않도록 스택 포인터($sp)를 내려 스택 프레임에 백업해야 합니다. 기저 조건(Base Case) 검사와 반환값 복원 규칙입니다.1. 피보나치 재귀 함수 어셈블리 코드
# int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }
.text
.globl fib
fib:
# 1. 스택 프레임 12바이트 확보
addi $sp, $sp, -12
sw $ra, 8($sp) # 복귀 주소 백업
sw $s0, 4($sp) # 인자 n 백업용
sw $s1, 0($sp) # fib(n-1) 결과 백업용
move $s0, $a0 # $s0 = n
# 2. 기저 조건 (n <= 1 이면 n 그대로 반환)
li $t0, 1
ble $s0, $t0, base_case
# 3. 재귀 1: fib(n - 1)
addi $a0, $s0, -1
jal fib
move $s1, $v0 # $s1 = fib(n - 1)
# 4. 재귀 2: fib(n - 2)
addi $a0, $s0, -2
jal fib # $v0 = fib(n - 2)
# 5. 합산
add $v0, $s1, $v0 # $v0 = fib(n - 1) + fib(n - 2)
j fib_end
base_case:
move $v0, $s0 # return n
fib_end:
# 6. 스택 복원 및 복귀
lw $s1, 0($sp)
lw $s0, 4($sp)
lw $ra, 8($sp)
addi $sp, $sp, 12
jr $ra