Đệ quy trong MIPS

Để thực hiện được đệ quy trong MIPS, điều quan tâm của chúng ta là các kết quả trung gian và thanh ghi địa chỉ $ra. MIPS cung cấp cho  chúng ta một stack pointer (thanh ghi $sp). Theo cơ chế stack thì cứ trước mỗi lần gọi thì ta giảm giá trị của thanh $sp, sau đó Push vào các kết quả trung gian cần nhớ và thanh ghi $ra. Sau lời gọi đệ quy thì ta lấy lại các kết quả trung gian xử lí tính toán và phục hồi lại thanh $ra, sau đó jr $ra là OK!

Nguyên nhân tại sao lại lưu thanh ghi $ra: Khi ta gọi thủ tục jal [ten-thu-tuc], thì lúc đó thanh ghi $ra tự động cập nhật lại địa chỉ phái sau lệnh jal, để chương trình sau khi thực hiện xong thủ tục thì chạy về thủ tục gọi hàm và thực hiện tiếp những lệnh sau nó. Khi đệ quy, tức là gọi lại thủ tục đó nhiều lần, nếu như ta không lưu lại thanh ghi $ra thì $ra sẽ được cập nhật mới sau mỗi lần gọi đệ quy. Vì thế nó sẽ không nhớ được đường về những lần gọi thủ tục trước lần gọi cuối cùng.
Và sau đây là một bài code mẫu tính giai thừa bằng đệ quy:
.data

  st_Nhap: .asciiz "Nhap vao so n: "
.text
main:


  addi $v0 $0, 5
  syscall
  addi $a0, $v0, 0
  jal giaithua
  addi $a0, $v0, 0
  addi $v0 $0, 1
  syscall


  addi $v0 $0, 10
  syscall
giaithua: # <=> $v0 = giaithua($a0)




  bne $a0, $0 , dequy 
  addi $v0, $0, 1
  jr $ra
  dequy:
    addi $sp, $sp, -8
    sw $a0, 0($sp)
    sw $ra, 4($sp)
    addi $a0, $a0, -1
    jal giaithua
        
    lw $a0, 0($sp)
    addi $a1, $v0, 0
    jal Nhan
    
    lw $ra, 4($sp)
    addi $sp, $sp, 8


  jr $ra 


Nhan:
  addi $sp, $sp, -4
  sw $ra, 0($sp)
  addi $v0, $0, 0
  LapNhan:
    slt $t0, $0, $a1
    beq $t0, $0, KTLapNhan
    add $v0, $v0, $a0
    addi $a1, $a1, -1
    j LapNhan
  KTLapNhan:


  lw $ra, 0($sp)
  addi $sp, $sp, 4
  jr $ra