Блог

Главная - Вопросы по программированию - Рекурсивная функция MIPS не работает должным образом

Рекурсивная функция MIPS не работает должным образом

#recursion #mips #factorial

#рекурсия #mips #факториал

Вопрос:

Я выполняю рекурсивную функцию factorial в MIPS. Вот код:

 fact: #a1 = n   a2 = res

addi $t1,$zero,1
beq $a1,$t1,end  # if n == 1 return res
#else
mul $a2,$a2,$a1
subi $a1,$a1,1

jal fact


end:
sb $a2,res
jr $ra

Проблема в том, что этот код работает только тогда, когда я пишу j fact вместо jal fact , по jal fact какой-то причине код выполняется бесконечно.

Комментарии:

1. Один шаг и посмотрите, что произойдет. Попробуйте использовать наименьший возможный рекурсивный пример, т.Е. n = 2.

2. Имейте в виду, что каждое jal из них будет перезаписывать предыдущее значение $ra новым обратным адресом. Поэтому, если вы хотите сохранить предыдущий адрес возврата, вы должны сделать это самостоятельно, например, временно поместив его в стек.

Ответ №1:

     fact: #a1 = n   a2 = res

addi $t1,$zero,1
beq $a1,$t1,end  # if n == 1 return res
#else
addi $sp, $sp, 8
sw $a1, 0($sp) #  in the top of the stack store the argument you called fact
sw $ra, 4($sp) # ra holds the return adress ( I do not know whether you know it)
mul $a2,$a2,$a1
subi $a1,$a1,1
jr $ra

jal fact
lw $a1, 0($sp) # load the value from memory adress that the top stack pointer shows to back to the register a1
lw $ra, 4($sp) 
addi $sp, $sp, 8 # delete current top , top-1 from the stack
jr $ra

end:
sb $a2,res
jr $ra