使用 MIPS 汇编语言理解递归

Question

我在课堂上，我们已经/正在讨论汇编语言中的递归。 我觉得我理解了递归，但是越多的人试图向我解释它，我就越觉得离它很遥远。

无论如何，我们的最后一张幻灯片有一个函数（用 C 语言？），老师说他会在课堂上介绍它，但要求我们学生在黑板上展示课堂上的其余部分。我感觉他一直在看着我，我害怕看起来很愚蠢。

你们能帮我在 MIPS 中编写这段代码并帮助我理解它吗？ 如果这太难了，我不知道

用 MIPS 汇编语言编写来查找修复（i，x），其中修复（i，x）是 递归地定义为：

int fix(int i, int x) // assume i > 0, x > 0
{
    if (x>0)
        return fix(i,x-1);
    else if (i>0)
        return fix(i-1, i-1)+1;
    else
        return 0;
}

谢谢你们，我的课是明天，我还是希望他永远不要打电话给我；但我想真正理解这些材料。

注意：这将是课堂练习，附有 0 学分。我觉得班上的每个人都已经知道如何做到这一点。

Answer 1

汇编语言与递归无关，它只是由于 C 语言以及调用约定和实现而起作用。只需在汇编程序中实现 C，而不关心递归。我想我在一个宠物项目 http://github.com/dwelch67/lsasim 上谈到了这一点，除非我改变它最后一课是手动将 C 中的递归转换为汇编程序。它不是 mips，所以不用担心这是一个家庭作业问题。

无论如何，开始的关键是简单地在汇编中实现 C。

例如，您有一个带有输入参数的函数。

int fix(int i, int x)

您需要声明自己的调用约定或使用现有的调用约定，要实现 C，这意味着您需要一些位置来存放输入参数，要么将它们压入堆栈，要么将它们带入寄存器。假设没有优化，您可以在整个函数中保留这些变量并在最后进行清理。因此，如果您需要在代码中的任何位置调用 ANY 函数（递归，调用相同的函数，是 ANY 的一个非常小的子集，但属于该类别并且不是特殊的），您需要保留这些变量。如果调用约定将它们带入堆栈，那么您就已经完成了，如果调用约定将它们带入寄存器，那么您需要在调用之前保留它们，并在调用之后恢复

push i
push x
implement call to function
pop x
pop i

并继续实现该函数。

就是这样，剩下的就自然而然了。

如果您碰巧注意到您作为示例创建的函数，在该函数内调用函数后没有需要保留输入变量的路径。并且输入变量被修改并用作下一次调用的输入。因此，对 C 代码实现的优化是不用担心保留这些变量。只需修改它们并传递它们即可。在调用约定中使用寄存器将是对此特定函数执行此操作的最简单方法。这是编译器在优化时无论如何都会做的事情（如果使用基于寄存器的调用约定则不保留）。

如果这就是所谓的，您也可以进行尾部优化。通常，当调用函数时，您可以使用指令通常执行的任何操作来执行“调用”，这与简单的跳转或分支不同，因为有一个返回值保存在某处。并且有某种返回函数可以撤消此操作并在调用后返回到指令。嵌套调用意味着嵌套返回值，跟踪所有返回值。在这种情况下，以及其他情况下，您在函数的执行路径中所做的最后一件事是调用另一个函数，您可以改为（取决于指令集）分支到该函数，而不必嵌套另一组返回值。以arm指令集为例：

某些代码调用第一个函数：

bl firstfun：

在arm中，bl表示分支链接。寄存器 14 将填充返回值，程序计数器将填充函数firstfun 的地址。

通常，如果您需要从函数调用函数，则需要保存 r14，以便可以从该函数返回，而无需尾部优化：

firstfun:
 ...
 push {r14}
 bl secondfun
 pop {r14}
 bx r14
 ...
secondfun:
  bx r14

bx lr 仅意味着分支到 r14 中的内容，在本例中是返回。优化看起来像这样，重要的是要注意，在第一个函数中，对第二个函数的调用是从第一个函数返回之前所做的最后一件事。这是本次优化的关键。

firstfun:
 ...
 b secondfun
 ...
secondfun:
  bx r14

b 只是表示分支，而不是分支链接，它只是修改 pc 而不会修改 r14 或任何其他寄存器或堆栈。两个实现的执行在功能上是相同的，外部函数调用firstfun，并且在正确的执行路径中有一个返回（bx r14）。

其他人指出，由于您将原始调用者返回零，因此该代码可能会完全优化自身而变得无用。

fix:
  return 0

Answer 2

就像上面的C一样把它分成3块。通过寄存器传递值 i 和 x 并在运行 if 检查并修改寄存器后调用自己。上述内容不应花费超过 30 行汇编程序来完成。如果我是一名更好的 MIPS 编码员，我会为你做这件事。它看起来像（是伪汇编程序），

fix:
  compare r0, 0
  branch greater than x_positive
  subtract r1,r1,1
  call fix
  return;
//  or just jump fix instead

x_positive:
  compare r1, 0
  branch greater than i_positive
  subtract r0, r0, 1
  subtract r1, r1, 1
  call fix
  return
// or just  jmp fix

i_positive:
  move return register, 0
  return

有趣的是，这将始终返回 0，如 C 中编写的:)

  fix:
    move return_register, 0
    return

Answer 3

虽然我反对只给出家庭作业问题的答案，但这里有一个等效的函数，可以找到 fix(i, x)，并带有示例调用（这个版本比 C 版本更高效） )：

fix:
        bgtz RetI
        xor $v0, $v0, $v0
        jr $ra
RetI:
        move $v0, $a0
        jr $ra

# example of calling fix
main:
        la $a0, 42
        la $a1, 21
        jal fix

这对您来说是一个教训，让您在尝试编写函数之前了解函数的用途:)