MIPS實作遞歸詳解(實作階乘) -Kaiqisan

大家好，都吃晚飯了嗎？我是Kaiqisan,是一個已經走出社恐的一般生徒,今天在繁忙的考研生活中抽出一點時間來寫這篇部落格，也算是我認為相對比較有價值，值得一寫的内容

例題：使用彙編語言完成下面代碼

// js語言
function fact(n) {
 	if (n < 1) {
    	 	return 1
 	} else {
     	return n * fact(n - 1)
	}
}
           

// c語言
int fact(int n) {
	if (n < 1) {
    	return 1;
	} else {
    	return n * fact(n - 1);
 	}
}
           

其中，參數n使用寄存器 $a0

fact:	
	addi $sp, $sp, -8 # (遞歸過程也會開辟)開辟空間
	sw $ra, 4($sp)
	sw $a0, 0($sp)

	# 條件判斷
	slti $t0, $a0, 1
	beq $a0, $zero, L1

 	# 傳回程式
 	addi $v0, $vo, 1
 	jr $ra

L1:	
	addi $a0, $a0, -1
	jal fact # 跳轉至callee,并修改$ra位址為下一條指令的位置

	lw $a0, 0($sp)
	lw $ra, 4($sp)
	addi $sp, $sp, 8
	mul $v0, $a0, $v0
	jr $ra
           

程式遞歸過程會先開辟好所有的空間，然後再開始業務計算。（假設我們傳入參數值為4）

|4|$top|3|$ra|2|$ra|

這裡 $top指的是程式最初的調用者

$ra指的是指令

jal fact

的下一行代碼的位置

每一次開辟新的位置的時候就給參數減一

在最後發現參數的值為1了，符合條件，跳轉到上一個callee，然後在$v0+1後就跳轉到下面，開始業務計算

每一次開始計算之前，都退一次棧，取出裡面的兩個字的資料，一份是下一次跳轉的位址，一份是目前的參數值

然後把最終傳回值 v 0 和 當 前 參 數 v0和目前參數 v0和目前參數a0相乘，傳回到上一個callee.

一直退棧…

直到

|4|$top|

這最後一跳在計算完成之後傳回程式的最終調用者，整個遞歸程式結束。

總結

這也是為什麼我們在用算法的時候為什麼最好不要使用遞歸的理由了，在彙編語言中，調用函數需要額外使用記憶體（雖然最後會被恢複），很容易就會影響執行效率。并且遞歸的本質就是棧，所有的遞歸程式都可以用非遞歸的方法來實作！