递归是通过移动堆栈指针寄存器($sp(来实现的。
我正在一个整数数组上创建一个快速排序算法。我正在使用这个C算法并将其转换为MIPS。然而，MIPS和递归确实非常困难。
我不确定如何将参数发送到递归调用QS中。我最近发现，通过将堆栈指针移动4个字节，我可以为调用堆栈中的每一帧更改$s寄存器。这将允许我更改每个堆栈帧的$s寄存器，这样我就不需要每个QS帧有一百万个变量。
我的问题是，我真的不知道如何以及何时在递归过程中设置和获取这些$sx值。
首先，让我们了解移动堆栈指针的意义：当您在高级语言中使用递归时，它所做的基本上是将当前函数调用的状态"保存"在"堆栈内存"中。要实现这一点，您必须：
- 保存程序的当前状态(所有变量/寄存器您正在"函数"的范围内使用(，在堆栈内存中
- "递归"调用函数(可能会修改您正在使用的所有寄存器(
- 当功能完成时，您必须恢复以前的状态并"释放"您分配的空间
但除此之外，我们还必须保存$ra的值，以跟踪上函数结束时我们应该去的地方。
下面是一个递归计算阶乘(n(的程序的简单示例：
.text
main:
# Calls Fact with Input ($a0) N = 10
li $a0, 10
jal fact
# prints the Output ($v0) Factorial(N)
move $a0, $v0
li $v0, 1
syscall
# exit
li $v0, 10
syscall
# Input: $a0 - N
# Output: $v0 - Factorial(N)
fact:
# Fact(0) = 1
beq $a0, 0, r_one
# Fact(N) = N * Fact(N-1) use recursion
# allocate 8 bytes in the stack for storing N, and $ra
addi $sp, $sp, -8
# stores N in the first, and $ra in the last position
sw $a0, 4($sp)
sw $ra, 0($sp)
# call Fact(N-1)
addi $a0, $a0, -1
jal fact
# Restore the values of N and $ra
lw $a0, 4($sp)
lw $ra, 0($sp)
# Free the 8 bytes used
addi $sp, $sp, 8
# Set the return value to be N * Fact(N-1) and return
mul $v0, $a0, $v0
jr $ra
# return 1;
r_one:
li $v0, 1
jr $ra
基本上，在实现代码时应该记住这一点。只需注意：
- 堆栈指针递减
- 您需要分配多少字节。在这个例子中，我使用了2个32位的整数，总共8个字节。这将取决于您需要存储多少变量及其大小
- 如何使用正确的索引使用lw和sw访问它们。此外，要注意记忆对齐
- 这不仅适用于递归。您可以使用堆栈内存来调用另一个使用正在使用的寄存器的函数(基本上与递归相同，只是不需要保存$ra(。还存储一个数组、一个结构等
编辑：
一些注意事项：
- 正确的方法是代码调用函数(分配和保存(，然后调用(恢复和释放(
- 了解您的代码，了解哪些变量需要保存(可能会被使用(