Рекурсия MIPS: как вычислить конечный результат из стека

Question

Моя задача - реализовать эгипетское умножение в ассемблере 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 являются разветвленными, или то, называется рекурсивно ...

---

/Edit:

Хорошо, кажется, что я понял, как реализовать что-то рекурсивно в 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, не добавляется. Как я могу это исправить?

Спасибо!

Answer 1

jal является инструкцией JUMP AND LINK, что означает, что он хранит адрес следующей инструкции в r31 и переходит к указанной метке. Вы могли бы сказать, что это (один /) способ делать вызовы подпрограмм в 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... 

Проблема с первым базовым случаем является то, что б все еще может быть 1 и дать результат, но вы возвращаетесь в любом случае, не используя значение.