MIPS递归:如何从堆栈计算最终结果

我的任务是递归地在MIPS汇编程序中实现埃及乘法 . 我想我理解了大部分相关内容,但我不能落后于一件事:最终结果如何计算?例如,在此代码中(取自this问题):

# int fact(int n)
fact:
subu    sp, sp, 32  # Allocate a 32-byte stack frame
sw  ra, 20(sp)  # Save Return Address
sw  fp, 16(sp)  # Save old frame pointer
addiu   fp, sp, 28  # Setup new frame pointer
sw  a0,  0(fp)  # Save argument (n) to stack

lw  v0, 0(fp)   # Load n into v0
bgtz    v0, L2      # if n > 0 jump to rest of the function
li  v0, 1       # n==1, return 1
j   L1      # jump to frame clean-up code

L2:
lw  v1, 0(fp)   # Load n into v1
subu    v0, v1, 1   # Compute n-1
move    a0, v0      # Move n-1 into first argument
jal fact        # Recursive call

lw  v1, 0(fp)   # Load n into v1
mul v0, v0, v1  # Compute fact(n-1) * n

#Result is in v0, so clean up the stack and return
L1:
lw  ra, 20(sp)  # Restore return address
lw  fp, 16(sp)  # Restore frame pointer
addiu   sp, sp, 32  # Pop stack
jr  ra      # return
.end    fact

如何/何时是两条线之间

jal fact

L2

曾经达到过?根据我的理解,L1 / L2分支,或者事实被称为递归...


/编辑:

好吧,我似乎想出了如何在MIPS中递归实现某些东西 . 但是,我有一个最后的问题:使用下面的代码,我的程序缺少一个“转向”,这意味着在计算最终结果时不考虑最后一个值 .

pharao:
    li $t0, 2       #load imm for division by 2
    lw $a0, fac_1       #load fac_1 into $a0
    lw $a1, fac_2       #load fac_2 into $a1
    li $t7, 0       #zero $t7
    li $t6, 1       #load 1 into $t6

    jal egypt       #jump to egypt
    j end




egypt:      
    subiu $sp,$sp,16    #space on stack for 4 values
    sw $ra,0($sp)       #store return address
    sw $a0, 4($sp)      #store fac_1
    sw $a1, 8($sp)      #store fac_2
    divu $a1, $t0       #div fac_2 by 2
    mflo $a1        #store quotient in $a1
    mfhi $a2        #store remainder in $a2
    sw $a2, 12($sp)     #store remainder on stack


    multu $a0, $t0      #multiply fac_1 by 2
    mflo $a0

    beq $a1, $t6, return    #base case

    jal egypt       #call egypt recursively

addingup:       
    lw $a0, 4($sp)      #load values from stack
    lw $a1, 8($sp)      #   "
    lw $a2, 12($sp)     #   "

    beqz $a2, return    #jump on if remainder is 0

    addu $t7, $t7, $a0  #add if remainder is 1      
return:     

    lw $ra, 0($sp)      #restore return address
    addiu $sp, $sp, 16  #inc stackpointer
    jr $ra

当我尝试使用值10和20运行程序时,结果($ t7中)为40,因为最后一个值160不会被添加 . 我怎样才能解决这个问题?

谢谢!

回答(1)

3 years ago

jal 是指令 JUMP AND LINK ,这意味着它存储下一条指令's address in r31 and jumps to the label given. You could say it'(一种/种)在MIPS汇编程序中执行子程序调用的方法 .

jr $ra 跳转到r31中包含的地址,这意味着它返回到 jal 之后的指令 . 如你所见,这是在 .end 之前完成的 .

简而言之, jal 是一个子程序调用,当调用返回时,它将执行 jal 之后的指令 .

在你编辑的问题中,你有点奇怪地检查基本情况,例如;

a = n >> 1;
b = n & 1;
if(a == 0)
   return 0;
...do calculation...

......当一个更好的基础案例时;

if(n == 0)
   return 0;
a = n >> 1;
b = n & 1;
...do calculation...

第一个基本情况的问题是b仍然可以是1并给出结果,但是无论如何都要返回而不使用该值 .