Понимание Recusion In MIPS

Question

Я просматривал прошлое задание и пытался следовать логике рекурсивных функций. Он просто передает вход в «факт», определяет, если> = 1, и снова передает его в цикл. В петле я запутался. Я понимаю, что при вызове функций часто бывает полезно сохранить данные с помощью sw и загрузить его с помощью lw, когда вы закончите. Однако цикл вызывает факт (который вызывает цикл снова) до ввода < 1. Как вы можете видеть в приведенном ниже коде, он постоянно сохраняет $ ra и ввод в том же месте. Обратите внимание, что код lw не используется до тех пор, пока рекурсия не будет выполнена.

Как это не перезаписывать старые данные? Вернули старые данные? Если это так, то как выбираете только два элемента, достаточно много раз, когда рекурсия используется? Какова цель $ v0 в этом коде?

fact: slti $t0, $a0, 1 # test for n < 1, n is user input 
     beq $t0, $zero, L1 # if n >= 1, go to L1 
     li $v0, 1 # return 1 
     jr $ra # return to instruction after jal 

L1: addi $sp, $sp, -8 # adjust stack for 2 items 
     sw $ra, 4($sp) # save the return address 
     sw $a0, 0($sp) # save the argument n 
     addi $a0, $a0, -1 # n >= 1; argument gets (n – 1) 
     jal fact # call fact with (n – 1) 
     lw $a0, 0($sp) # return from jal: restore argument n 
     lw $ra, 4($sp) # restore the return address 
     addi $sp, $sp, 8 # adjust stack pointer to pop 2 items 
     mul $v0, $a0, $v0 # return n * fact (n – 1) 
     jr $ra # return to the caller 

Answer 1

Это классический пример манипуляции стеком.

Каждый раз, когда функция выполняет, он увеличивает стек и сохраняет $ra и $a0 в новой выделенной позиции.

Вы можете увидеть это, отметив, что $ra и $a0 выделяются относительно $sp (указатель стека ).

Каждый раз, когда функция выполняет стек, увеличивается путем вычитания 8 от $sp или достаточно места для двух слов. Аналогично, когда функция выходит из стека, уменьшается, добавляя 8 в $sp.

---

Подумайте, как это:

Предположим, мы хотим вычислить 5 !.

Стек на каждый звонок до fact хранит как $a0, так и $ra. После 5 звонков fact стеки будут выглядеть следующим образом:

$a0: 5 
$ra: back to main 
---- 
$a0: 4 
$ra: back to fact 
---- 
$a0: 3 
$ra: back to fact 
---- 
$a0: 2 
$ra: back to fact 
---- 
$a0: 1 
$ra: back to fact 
---- 

После того, как базовый случай выполняет ($a0 = 1) стек начинает сокращаться. Стол $a0 = 1 возвращает 1 в $v0, и когда мы отправляемся на загрузку $a0, получаем 2, потому что мы уже сжимаем стек. Поэтому мы умножаем 2 на 1, а затем возвращаем это значение. Тот же процесс повторяется в следующем стеке, где мы берем 2, возвращенный в $v0, и умножаем его на 3, который мы загружаем из стека, и возвращаем 6 в $v0.

Надеюсь, здесь вы можете увидеть, как:

addi $a0 $zero 5 
jal fact 

вернуться бы 120 в $v0.