递归斐波那契 MIPS

Question

我开始阅读MIPS，以更好地了解我的C ++和C代码在计算机皮肤下的工作方式。我从递归函数（斐波那契函数）开始。 C代码为：

int fib(int n) {
if(n == 0) { return 0; }
if(n == 1) { return 1; }
return (fib(n - 1) + fib(n - 2));
}

MIPS代码：

fib:
addi $sp, $sp, -12 
sw $ra, 8($sp) 
sw $s0, 4($sp)

addi $v0, $zero, $zero
beq $a0, $zero, end
addiu $v0, $zero, 1
addiu $t0, $zero, 1 
beq $a0, $t0, end
addiu $a0, $a0, -1
sw $a0, 0($sp) 
jal fib #fib(n-1)
addi $s0, $v0, $zero 
lw $a0, 0($sp) 
addiu $a0, $a0, -1
jal fib #fib(n-2)
add $v0, $v0, $s0

end:
lw $s0, 4($sp)
lw $ra, 8($sp) 
addi $sp, $sp, 12
jr $ra

当n＆gt; 1时，直到代码达到第一个JAL指令。接下来会发生什么？它返回到fib标签忽略下面的代码（fib（n-2）呼叫永远不会执行吗？）？如果发生这种情况，则$ sp指针再次减小3个单词，并且周期将进行直到n＆lt; = 1。当第一次JAL达到指令时，我无法理解它的工作原理。

Answer 1

你能理解 C 中的递归是如何工作的吗？

从某种意义上说，递归有两个组成部分：前向部分和后向部分。在前向部分中，递归算法计算递归之前的事物，而在后向部分中，递归算法在递归完成后计算事物。在这两个部分之间，有递归。

请参阅此答案： https://stackoverflow.com/a/71551098/471129

斐波那契的执行稍微复杂一些递归两次，而不是像上面的列表打印示例中那样只递归一次。

但是，原理是相同的：有递归之前完成的工作，也有递归之后完成的工作（两者都可以退化）。之前的部分发生在递归执行之前的代码，并且递归构建堆栈帧，这些堆栈帧是递归尚未完成之后工作的占位符。之后的部分发生在堆栈帧被释放并且递归调用之后的代码被执行时。

在任何给定的调用链中，前向部分一直持续到 n 为 0 或 1，然后算法开始返回到堆栈调用者，对于这些调用者，后向部分将进入展开堆栈帧，直到它返回到原始调用者（可能是 main），而不是某些递归 fib 调用者。同样，由于使用两次递归调用而不是像更简单的示例中的一次，因此变得复杂。

对于 fib，之前完成的工作是倒计数（按 -1 或 -2）直到达到 0 或 1。递归之后所做的工作就是将之前的两个结果相加。递归本身有效地暂停了对当前值的 fib 的调用或激活，以便在递归调用完成时恢复。

---

MIPS算法中的递归是相同的；但是，函数操作分布在 C 中隐含的多个机器代码指令上。

---

建议单步执行对 fib(2) 的调用，作为一个非常小的示例，可以帮助您了解那里发生了什么. 建议首先在 C 中执行此操作 - 单步执行，直到外部 fib 调用完全完成并返回到调用测试函数（例如 main）。

为了使 C 版本更容易在调试器中查看，您可以使用此版本：

int fib(int n) {
    if (n == 0) { return 0; }
    if (n == 1) { return 1; }
    int fm1 = fib(n-1);
    int fm2 = fib(n-2);
    int result = fm1 + fm2;
    return result;
}

使用等效的 C 版本，您将能够检查 fm1、fm2 ，以及单步执行期间的结果。这将使它更容易遵循。

接下来，在汇编版本中执行相同的操作。调试单步以观察 fib(2) 的执行，并与 C 中的等效项进行比较。

---

还有另一种思考递归的方法，即忽略递归，假装递归调用是对某些不相关的函数实现恰好产生了递归函数的正确结果；这是这样一个非递归函数：

int fib(int n) {
    if (n == 0) { return 0; }
    if (n == 1) { return 1; }
    int fm1 = fibX(n-1);   // calls something else that computes fib(n-1)
    int fm2 = fibX(n-2);   //   "
    int result = fm1 + fm2;
    return result;
}

使用此代码，并假设 fibX 简单地正常工作以返回正确的结果，您可以严格专注于一个级别的逻辑，即，这个fib的主体，根本不考虑递归。

请注意，我们可以在汇编语言中执行相同的操作 - 尽管错误/拼写错误的机会总是比 C 语言中的大得多，因为您仍然必须操作堆栈帧并保留关键存储以供调用后稍后使用。

---

您发布的代码存在转录错误，使其与 C 版本不同。它所做的相当于 C 语言：

return fib(n-1) + fib(n-1);

---

让我们回到这个更明确的版本：

int fib(int n) {                  // n defined upon entry
    if (n == 0) { return 0; }
    if (n == 1) { return 1; }
    int fm1 = fib(n-1);           // fm1 defined
    int fm2 = fib(n-2);           // n used to compute n-2
    int result = fm1 + fm2;       // fm1 used
    return result;
}

对于汇编语言，必须执行变量分析，以便我们使用正确的寄存器和堆栈帧内存。

首先，让我们观察一下 n 在函数调用中是“活动”的，即 fib(n-1) 的函数调用。这是一个重要的属性。函数调用会清除某些寄存器，因此保留在函数调用之前定义并在函数调用之后使用的内容非常重要。这里 n 的值被定义为参数，因此可以认为在输入时就已经定义了。它用于执行 fib(n-1)，这并不重要，但它也用于执行 fib(n-2) — 计算 n-2 并且该计算在调用 fib(n-1) 之后进行。因此，n 需要特殊的存储空间，以便在第一次函数调用后仍能保存下来。

函数调用中还有哪些活动？它是 fm1，因为它在调用 fib(n-2) 之前定义并在调用之后使用。因此，fm1 也需要函数存活存储。

还有什么？我们在 C 中看不到它，但在汇编中，返回地址作为附加函数参数向我们公开，并且像 n 一样，它被认为是在函数入口处定义的。该传入参数值（返回地址）必须在两次函数调用中都存在，因为它在最后用于完成返回操作。

无论是使用具有显式变量的版本还是使用 fib(n-1) + fib(n-2) 中隐式内部临时变量的简单版本，这种活性/存储分析都是必要的。

让我们进一步注意，此分析对于 fibX 非递归版本是相同的，因为寄存器保存的所有要求都来自函数调用，而与递归无关。 （如果我们知道调用者和被调用者的实现，则有机会优化调用约定，但我们选择在这些学习场景中不使用这些）。

因此，我们需要做的是创建一些堆栈空间供函数使用，并在该堆栈空间中存储$ra（即返回地址）和$a0 code>，即 n，并且还为变量 fm1（或该版本中的临时变量）提供空间。稍后，fm1 在定义后需要存储到内存中，而 n 需要从内存中重新加载才能计算 n-2 ，用于下一次递归调用。在第二次递归调用之后，可以重新加载fm1，计算返回值，最后重新加载返回地址，释放堆栈帧，函数可以返回到其调用者。

我们还要注意，相比之下，fm2 和 result 相对简单，两者都不需要在函数调用后继续存在，因此它们可以使用调用破坏寄存器或从它们所在的寄存器中使用出现。