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|

这最后一跳在计算完成之后返回程序的最终调用者，整个递归程序结束。

总结

这也是为什么我们在用算法的时候为什么最好不要使用递归的理由了，在汇编语言中，调用函数需要额外使用内存（虽然最后会被恢复），很容易就会影响执行效率。并且递归的本质就是栈，所有的递归程序都可以用非递归的方法来实现！