Recusion에 대한 이해 MIPS에서

Question

나는 과거 할당을 검토 중이었고 재귀 함수의 논리를 따르려고했습니다. 단순히 입력을 "사실"로 전달하고> = 1인지 판단하고 다시 루프로 전달합니다. 그것은 내가 혼란스러워하는 루프에 있습니다. 함수를 호출 할 때 sw를 사용하여 데이터를 저장하고 완료하면 lw로로드하는 것이 좋습니다. 그러나 루프는 사실 까지 fact (루프를 다시 호출 함)를 호출합니다. 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합니다 (스택 포인터)에 상대적으로 할당하는 것을주의하여 볼 수 있습니다.

함수가 실행될 때마다 을 $sp에서 뺀 다음 두 단어에 대해 충분한 공간을 확장하여 스택을 확장합니다. 마찬가지로 함수가 스택을 종료 할 때 8을 $sp에 추가하여 축소됩니다.

---

는 다음과 같이 생각 :

이

한다고 가정 우리가 5 계산할!

fact을 호출 할 때 스택에 $a0과 $ra이 모두 저장됩니다. fact-5 호출 후 스택은 다음과 같을 것이다 : 스택이 수축하기 시작베이스 케이스 실행한다 ($a0 = 1)을 한번

$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로드 할 때 우리는 이미 스택을 축소 했으므로 2을 얻습니다. 그래서 2에 1을 곱한 다음 그 값을 반환합니다. 동일한 처리가 다음 스택 프레임에서 반복되고 2은 $v0으로 반환되고 스택에서로드 한 3을 곱하여 6을 $v0에 반환합니다.

addi $a0 $zero 5 
jal fact 

이 $v0에 120을 반환 :

는 희망이 여기에서 당신은 어떻게 볼 수 있습니다.