Pie*_*zza 2 recursion assembly function mips
我是 MIPS 的新手（因为我开始为我的大学学习 MIPS 汇编）并且我在理解递归函数如何在 MIPS 中工作时遇到了问题。
例如，我有这个程序（用 C 语言）用 MIPS 编写：
int fact (int n)
{
if (n < 1) return 0;
else return n * fact(n - 1);
}
有人可以用这个或另一个递归函数的例子帮助我并解释它是如何工作的吗？
我想分享的第一件事是，将其转换为 MIPSfact的复杂性来自于仅仅存在函数调用，而不是因为涉及递归 -恕我直言，递归是一种红鲱鱼。为此，我将说明一个非递归函数，它具有您所说的递归函数的每一点复杂性：
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在函数调用 (to other)之后是必需的，因为在该函数调用返回 的右侧操作数之前，我们无法进行乘法运算*。
因此，n（to 的左操作数*）必须在对 的函数调用中存活下来other，而在$a0它中则不会——因为我们自己的代码将重新调整用途$a0以调用other(n-1)，这n-1必须进入$a0。
此外，（在 C 中，隐式）参数$ra保存返回给我们的调用者所需的返回地址值。other类似地，调用将重新调整$ra寄存器的用途，清除其先前的值。
因此，此函数（您的或我的）需要两个值才能在其主体内的函数调用（例如对 的调用other）中存活下来。
解决方案很简单：我们需要的值（存在于寄存器中，这些值被我们正在做的事情重新定位或删除，或者被调用者可能会这样做）需要移动或复制到其他地方：在函数调用中幸存下来的地方。
内存可以用于此目的，并且我们可以使用堆栈为这些目的获取一些内存。
基于此，我们需要创建一个堆栈帧，在调用other. $ra必须保存条目（然后重新加载），以便我们使用它返回；此外，n需要保存初始值，以便我们可以将其用于乘法。（堆栈帧通常在函数序言中创建，并在函数尾声中删除。）
与机器代码（甚至一般的编程）中的情况一样，还有其他处理事物的方法，尽管要点是相同的。（这是一件好事，优化编译器通常会根据特定情况寻找最佳方法。）
递归的存在与否不会改变我们将其转换为汇编/机器语言所需的基本分析。递归极大地增加了堆栈溢出的可能性，但不会改变这种分析。
需要明确的是，递归要求使用动态可扩展的调用堆栈——尽管所有现代计算机系统都提供了这样的调用堆栈，因此这一要求很容易被今天的系统遗忘或掩盖。
对于没有递归的程序，调用栈不是必需的——局部变量可以分配给函数私有的全局变量（包括返回地址），而且这是在某些旧系统上完成的，比如 PDP-8，它没有提供特定的对调用堆栈的硬件支持。
使用堆栈内存传递参数和/或寄存器不足的系统可能不需要本答案中描述的分析，因为变量已经存储在内存中，可以在嵌套函数调用中幸存下来。
正是现代寄存器丰富的机器上的寄存器分区产生了上述分析的要求。这些寄存器丰富的机器在 CPU 寄存器中传递参数和返回值（大部分），这是有效的，但有时需要进行复制，因为寄存器从一个功能重新用于另一个功能。
| 归档时间： |
|
| 查看次数： |
319 次 |
| 最近记录： |