递归斐波那契 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>1

时，它将一直进行，直到代码到达第一个

jal

指令。接下来发生什么？它返回到

fib

标签，忽略下面的代码（fib(n-2) 调用永远不会被执行？）？如果发生这种情况，

$sp

指针会再次减少3个字，循环直至

n<=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

和

result

。这将使您更容易遵循。

接下来，在汇编版本中执行相同的操作。调试单步以观察

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);