递归函数如何在 MIPS 中工作？

Question

我是 MIPS 的新手（因为我开始为我的大学学习 MIPS 汇编），我在理解递归函数在 MIPS 中的工作原理时遇到了问题。

例如，我有这个程序（用 C 语言）用 MIPS 编写：

int fact (int n)
{
   if (n < 1) return 0;
   else return n * fact(n - 1);
}

谁能用这个或另一个递归函数的例子帮助我，并解释一下它是如何工作的？

Answer 1

我想分享的第一件事是，将其转换为 MIPS 的复杂性来自单纯的函数调用，而不是因为涉及递归 — fact递归是恕我直言，转移注意力。为此，我将说明一个非递归函数，它具有您所说的递归函数的每一点复杂性：

int fact (int n)
{
   if (n < 1) return 0;
   else return n * other(n - 1);    // I've changed the call to "fact" to function "other"
}

我的修改不再是递归的！但是，此版本的 MIPS 代码看起来与 fact 的 MIPS 代码相同（当然，jal fact 更改 jal other 除外）。这是为了说明翻译的复杂性是由于函数内部的调用，与调用的对象无关。（虽然 YMMV 具有优化技术。）

要理解函数调用，你需要理解：

程序计数器：程序如何与程序计数器交互，尤其是在函数调用的上下文中..
参数传递
一般来说注册约定

在 C 中，我们有显式参数。当然，这些显式参数也出现在 assembly/machine 语言中——但也有一些在机器代码中传递的参数在 C 代码中不可见。这些示例是 return 地址值和堆栈指针。

这里需要的是对函数的分析（与递归无关）：

参数n将在$a0函数入口处。 n 的值在函数调用之后是必需的（到 other），因为在函数调用 return 之前我们不能乘以 * 的右手操作数。

因此，n（* 的左手操作数）必须在对 other 的函数调用后继续存在，而在 $a0 中则不会——因为我们自己的代码将重新利用 $a0 以调用 other(n-1)，因为 n-1 必须为此进入 $a0。

此外，（在 C 中，隐含的）参数 $ra 保存 return 所需的 return 地址值给我们的调用者。类似地，对 other 的调用将重新调整 $ra 寄存器的用途，清除其先前的值。

因此，这个函数（你的或我的）需要两个值才能在其主体内的函数调用（例如对 other 的调用）中存活。

解决方案很简单：我们需要的值（存在于寄存器中的值会被我们正在做的事情或被调用者可能做的事情改变用途或清除）需要移动或复制到其他地方：某个可以生存的地方函数调用。

为此可以使用内存，并且，我们可以使用堆栈为这些目的获取一些内存。

基于此，我们需要为调用 other 后需要的两件事（否则会被清除）创建一个堆栈帧，其中包含 space。条目 $ra 必须保存（稍后重新加载）以便我们将其用于 return；此外，需要保存初始 n 值，以便我们可以将其用于乘法。（堆栈帧通常在函数序言中创建，并在函数结尾中删除。）

就像机器代码（甚至一般编程）中经常出现的情况一样，还有其他处理事物的方法，尽管要点是相同的。（这是一件好事，优化编译器通常会根据特定情况寻找最佳方法。）

存在或不存在递归不会改变我们需要将其翻译成 assembly/machine 语言的基本分析。递归显着增加了堆栈溢出的可能性，但不会改变此分析。

附录

需要明确的是，递归要求使用动态可扩展的调用堆栈——尽管所有现代计算机系统都提供这样的调用堆栈，因此这一要求很容易被遗忘或在今天的系统中被掩盖。

对于没有递归的程序，调用堆栈不是必需的——局部变量可以分配给函数私有的全局变量（包括 return 地址），这在某些较旧的系统上已经完成，例如PDP-8，它没有为调用堆栈提供特定的硬件支持。

使用堆栈内存传递参数的系统 and/or 寄存器不足可能不需要此答案中描述的分析，因为变量已经存储在内存中，在嵌套函数调用后仍然存在。

现代寄存器丰富的机器上的寄存器分区产生了上述分析的要求。这些寄存器丰富的机器在 CPU 寄存器中传递参数和 return 值（大部分），这很有效，但有时需要进行复制，因为寄存器从一个功能重新用于另一个功能。

Answer 2

实现您描述的功能的一种方法是使用 addi 的内存分配来移动堆栈指针以分配（在开始时）和释放（在结束时）一些堆栈 space.然后 sw 指令可以将寄存器保存到 space 中。在通话后使用 lw 恢复它们，当您准备好 return 时使用 and/or。所以我们可以从这条指令开始分配一些内存：

addi $sp, $sp, -8 in $sp register, we sum -8

这是，我们需要 8 个字节，$ra return 需要 4 个字节，int n 需要 4 个字节。现在，我们按以下方式分配：

sw $a0, 4($sp) #we are saving the int with register $a0 in position 4
sw $ra, 0($sp) #we are saving the return address with address $ra in position 0

现在，我们需要一个临时变量来存储上面比较中的1。那么我们有：

addi $t0, [=15=], 2 in $t0 register, we sum 2 to [=19=]

现在比较操作数是slt，在我们的例子中：

slt $t0, $a0, $t0 in $t0 register, we compare the value contained in $a0 register with that in $t0 register, if true $t0 is 1, else is 0

因为如果$t0为零，我们需要有如下的跳转结构（注意else是一个标号，这是一个按规则要遵循的结构）： obs.: $0 用于存储零

beq $t0, [=17=], $t0, else in $t0 we see if it's zero, if so, we continue our program, if not, we go to another instruction, this is, else.

继续，我们现在要return0，如下：

`addi $v0, [=22=], 0

最后我们必须恢复我们非常清楚的堆栈。

对于标签else，我们从我们需要n变成n-1的概念开始，方式如下：

`addi $a0, $a0, -1 #this is, we add $a0 and -1 to $a0

我们必须使用 jal fact 因为很明显我们有一个递归。

下一步就是恢复我们知道的returnra和int n的地址，还有堆栈。很明显我们有一个乘法，对于这个主题，我们将应用下一条指令：

`mul $v0, $a0, $v0 #this is, we multiply $a0 with $v0, remembering that v0 stores the fact(n-1):

`mul $v0, $a0, $v0 #multiplies n and fact(n-1)

我们必须记住，使用 jr $ra 到 return.

是必要的

我希望，我已经清除了一点。

递归函数如何在 MIPS 中工作？

How a recursive function works in MIPS?

recursion

assembly

function

mips

附录