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

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

int fact (int n)
{
   if (n < 1) return 0;
   else return n * fact(n - 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 代码看起来与您的 MIPS 代码相同。fact（当然，例外的是jal fact这改变了jal other）。这是为了说明翻译 this 的复杂性是由于函数内的调用造成的，与调用者无关。 （虽然 YMMV 具有优化技术。）

要理解函数调用，您需要了解：

• 程序计数器：程序如何与程序计数器交互，特别是在函数调用的上下文中。
• 参数传递
• 一般而言，寄存器约定

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

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

参数n将在$a0在函数入口处。的价值n函数调用后需要（到other），因为在该函数调用返回右侧操作数之前我们无法进行乘法运算*.

所以，n（左手操作数*) 必须在函数调用后继续存在other，并在$a0它不会——因为我们自己的代码将重新调整用途$a0为了打电话other(n-1), as n-1必须进入$a0为了那个原因。

另外，（在 C 中，隐式）参数$ra保存返回给调用者所需的返回地址值。致电给other同样，将重新调整用途$ra寄存器，清除其先前的值。

因此，这个函数（你的或我的）需要两个值才能在其体内的函数调用中幸存下来（例如调用other).

解决方案很简单：我们需要的值（存在于寄存器中，这些值被我们正在做的事情或被调用者可能做的事情重新利用或擦除）需要移动或复制到其他地方：在函数调用中将幸存的地方。

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

基于此，我们需要创建一个堆栈帧，在调用后为我们需要的两件事提供空间（否则会被清除）other。入口$ra必须保存（并稍后重新加载）以便我们使用它返回；另外，最初的n需要保存值，以便我们可以将其用于乘法。 （堆栈帧通常在函数序言中创建，并在函数尾声中删除。）

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

递归的存在或不存在不会改变我们将其翻译成汇编/机器语言所需的基本分析。递归极大地增加了堆栈溢出的可能性，但不会改变此分析。

Addendum

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

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

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

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