调用类似于 MIPS 中二叉树的递归过程
Recursive Procedure Whose Calls Resemble a Binary Tree in MIPS
我正在做作业，但很难理解如何用 C 语言正确编写以下问题。
int choose(int n, int k){
if (k == 0) {
return 1;
} else if (n == k) {
return 1;
} else if (n < k) {
return 0;
} else {
return choose(n-1, k-1) + choose(n-1, k);
}
}
我的想法是在每次调用时使用三个寄存器将值存储到堆栈中 $s0, $s1, $s2，其中 $s0 将包含更新后的值 n； $s1 将保持 k 的值；并且 $s2 将在第二个 choose(n-1, k) 中保留 k 的值，因为该值只会在 parent 调用更改它时减少。我选择这个的原因是因为 k 的值没有从这个调用中的每个调用中减去，它应该是相同的，直到 parent 在上一个调用中递减它。
这是我正在尝试执行的 Choose 程序。当然，问题是我没有得到正确答案。
Choose:
#store current values onto stack
addi $sp, $sp, -16
sw $ra, 0($sp)
sw $s0, 4($sp)
sw $s1, 8($sp)
sw $s2, 12($sp)
#check values meet criteria to add to $v0
beq $s1, [=11=], one
beq $s0, $s1, one
blt $s0, $s1, zero
beq $s2, [=11=], one
#no branches passed so decrement values of n and k
subi $s0, $s0, 1
subi $s1, $s1, 1
#move values of registers to $a's for argument passing
move $a0, $s0
move $a1, $s1
jal Choose #call procedure again
#this is where I'm having my problems
#not sure how to loop the procedure to get
#the second half of the equation Choose(n-1,k)
#which is the reason for the next 2 lines of code
move $a2, $s2
jal Choose
add $v0, $v0, $v1
j Choose_Exit
#add one to $v1 from branch passed
one:
addi $v1, $v1, 1
j Choose_Exit
#branch returns 0
zero:
addi $v1, $v1, 0
j Choose_Exit
#return values to caller from stack
Choose_Exit:
lw $s2, 12($sp)
lw $s1, 8($sp)
lw $s0, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 16
jr $ra
所以我在理解如何正确实施此递归过程两次以将它们加在一起时遇到问题。我可以理解如何在 MIPS 中创建递归过程来执行阶乘，因为这始终是任何语言的递归定义。但是使用带有不同参数的递归，然后将它们全部加在一起，这让我很困惑。
当写在纸上时，我了解到这个程序可以用 parent 和 children 的二叉树来表示。 parent 是单个函数 Choose(n,k)，children 是 Choose(n-1, k-1) + Choose(n-1, k)，一旦 if 语句的叶子 children 分支之一，它将一个数字传递给 parent，后者将等待其他被调用者部分添加到 return 其值，等等等等。
任何帮助我指出我的方法做错了什么的正确方向都会很棒。我理解开头，我理解结尾，只需要一些帮助来帮助理解中间最重要的部分。
你们很接近。
您为 return 地址、arg1、arg2 建立了堆栈框架，并保存了 return 值。
您的主要障碍是，在第一次调用您的函数后，您必须将 $v0 保存到堆栈上 [如玛格丽特上面提到的]。
这是一些我认为可以使用的代码。它与您的非常相似，但我是从头开始编写的。它具有第一个调用的 return 值的正确 "push"/"pop"。
我确实为早期逃逸 [non-recursive] 案例添加了一个小优化：它们省略了创建堆栈帧。
无论如何，这里是：
#@+
# int
# choose(int n, int k)
# {
#
# if (k == 0)
# return 1;
#
# if (n == k)
# return 1;
#
# if (n < k)
# return 0;
#
# return choose(n - 1,k - 1) + choose(n - 1,k);
# }
#@-
.text
# choose -- choose
#
# RETURNS:
# v0 -- return value
#
# arguments:
# a0 -- n
# a1 -- k
#
# registers:
# t0 -- temp for 1st return value
choose:
beqz $a1,choose_one # k == 0? if yes, fly
beq $a0,$a1,choose_one # n == k? if yes, fly
blt $a0,$a1,choose_zero # n < k? if yes, fly
# establish stack frame (preserve ra/a0/a1 + space for v0)
sub $sp,$sp,16
sw $ra,12($sp)
sw $a0,8($sp)
sw $a1,4($sp)
addi $a0,$a0,-1 # get n - 1 (common to both calls)
# choose(n - 1,k - 1)
addi $a1,$a1,-1 # get k - 1
jal choose
sw $v0,0($sp) # save 1st return value (on _stack_)
# choose(n - 1,k)
addi $a1,$a1,1 # get k (from k - 1)
jal choose
lw $t0,0($sp) # "pop" first return value from stack
add $v0,$t0,$v0 # sum 1st and 2nd values
# restore from stack frame
lw $ra,12($sp)
lw $a0,8($sp)
lw $a1,4($sp)
add $sp,$sp,16
jr $ra # return
choose_one:
li $v0,1
jr $ra
choose_zero:
li $v0,0
jr $ra
更新：
First off, I like how you noted the procedure as you did before you called it. I'm going to steal that!
请客！它来自多年编写asm。有关如何写好 asm 的初步想法，请参阅我的回答：
I've tried this and it works. I need to experiment with your code to understand why the stack is manipulated when it is (always thought it had to be at the very beginning and end of a proc).
通常，栈帧是在proc开始时建立并在proc结束时恢复。基于已经建立的框架，您处理 "quick escape" [non-recursive] 案例的代码 是 正确的。
这只是一个小的优化。但是，这是因为 mips 有如此多的寄存器，对于小函数，我们甚至不需要堆栈帧，特别是如果函数是 "leaf" 或 "tail"（即它不调用任何其他函数）。
对于较小的 [non-recursive] 函数，有时我们可以使用仅保留 $ra 的单字堆栈框架（例如）：fncA 调用 fncB , 但 fncB 是一片叶子。 fncA 需要框架，但 fncB 不需要 。事实上，如果我们控制这两个功能并且我们知道 fncB 不会修改给定的临时寄存器（例如$t9), 我们可以在那里保存 return 地址而不是在 fncA:
中创建堆栈帧
fncA:
move $t9,$ra # preserve return address
jal fncB # call fncB
jr $t9 # return
fncB:
# do stuff ...
jr $ra # return
通常，我们不能依赖 fncB 保留 $t9，因为根据 mips ABI，fncB 可以自由 modify/trash 任何寄存器是不是$sp或$s0-$s7。但是，如果我们精心设计函数，使我们认为 fncB 是 "private" 到 fncA（例如，像 C static 函数，只有 fncA 可以访问), 我们可以随心所欲。
信不信由你，fncA 以上 是 ABI 符合。
给定的 被调用者（例如 fncA）不需要 $ra [为了[缘故] of] 它的 来电者 ，只是为了它自己。而且，重要的是$ra里面的值，而不是具体的寄存器。被调用者只需要保留 $s0-$s7，确保 $sp 在退出时具有与入口相同的值，并且它 return 到调用者中的正确地址 [jr $t9 确实如此——因为它有 值 ，当 fncA 被调用时，它在 $ra 中。
I like your use of the temp register.
需要一个额外的寄存器，因为在 mips 中，我们可以不能从内存操作数进行算术运算。 mips 只能做 lw/sw。 （即）没有这样的东西：
add $v0,$v0,0($sp)
我将 $t0 用于 simplicity/clarity，因为当您需要临时调节器时，通常使用 $t0-$t9。使用$t0时的代码"reads better"。但是，这只是一个约定。
在mips ABI中，$a0-$a3可以修改，$v1也可以修改，只需要保留$s0-$s7。并且，"modification" 意味着它们可以用来保存任何值或用于任何目的。
在上面的link中，注意strlen递增$a0直接找到字符串的结尾。它使用 $a0 是为了一个有用的目的，但是，就调用者而言，$a0 被 strlen "trashed"。这种用法是 ABI conforming.
在 choose 中，我几乎可以使用 任何 寄存器：$v1、$a2-$a3 而不是 $t0。事实上，在 choose 中的那个特定点，不再需要 $a0，因此它可以用来代替 $t0。尽管对于 choose，我们 非 -ABI 符合（因为我们 save/restore $a0-$a1），这在 choose 中是可行的，因为我们从函数 epilog [stack frame pop] 恢复 $a0 的原始值，保留函数的递归性质。
正如我所说，$t0-$t9 是用于 scratch space 的常用寄存器。但是，我已经编写了使用所有 10 个函数的函数，并且仍然需要更多（例如，使用 Bresenham 圆算法绘制到帧缓冲区中）。 $v0-$v1 和 $a0-$a3 可以用作临时寄存器以获得额外的 6。如有必要，$s0-$s7 可以保留在堆栈帧中，只是为了释放它们以用作更多临时寄存器.
免责声明：我重写了汇编代码没有检查它。
- 有一些延迟槽需要考虑，这样可以更好地巧妙地使用它们并使其显式化，以避免在分支指令之后聚合隐式 nop 指令。
- 颠倒 choose(n - 1,k - 1) 和 choose(n - 1,k) 之间的调用顺序，以便更智能地使用 $a0 和 $a1 以及堆栈。
- 限制仅调用 choose(n - 1,k) 的堆栈使用，并使用尾调用调用 choose(n - 1,k - 1)。
- 堆叠a0-1而不是a0的值更有意义。
- 我们将所有内容累加到 $v0 中，而不是堆叠它。我们将 $t0 作为本地结果添加到 $v0 中，因为它很便宜，而我们可以通过直接使用 $v0 来丢弃它。
- 因此，总体变化应该使 icache 更快乐地使用更少的指令，并使 dcache 更快乐地使用更少的堆栈 space。
汇编代码：
#@+
# int
# choose(int n, int k)
# {
#
# if (k == 0)
# return 1;
#
# if (n == k)
# return 1;
#
# if (n < k)
# return 0;
#
# return choose(n - 1,k - 1) + choose(n - 1,k);
# }
#@-
.text
# choose -- choose
#
# RETURNS:
# v0 -- return value
#
# arguments:
# a0 -- n
# a1 -- k
#
# registers:
# t0 -- temp for local result to accumulate into v0
choose:
j choose_rec
addui $v0, $zr, 0 # initialize $v0 to 0 before calling
choose_rec:
beqz $a1,choose_one # k == 0? if yes, fly
addui $t0,$zr,1 # branch delay-slot with $t0 = 1
beq $a0,$a1,choose_one # n == k? if yes, fly
nop # branch delay-slot with $t0 = 1 already done
blt $a0,$a1,choose_zero # n < k? if yes, fly
addui $t0,$zr,0 # branch delay-slot with $t0 = 0
# establish stack frame (preserve ra/a0/a1)
sub $sp,$sp,12
addui $a0,$a0,-1 # get n - 1 (common to both calls)
sw $ra,8($sp)
sw $a0,4($sp)
jal choose_rec # choose(n - 1,k)
sw $a1,0($sp)
# restore from stack frame
lw $ra,8($sp)
lw $a0,4($sp)
lw $a1,0($sp)
add $sp,$sp,12
# choose(n - 1,k - 1)
j choose_rec # tail call: jump instead of call
addi $a1,$a1,-1 # get k - 1
choose_one:
choose_zero:
jr $ra # return
addui $v0,$v0,$t0 # branch delay-slot with $v0 += $t0
我正在做作业，但很难理解如何用 C 语言正确编写以下问题。
int choose(int n, int k){
if (k == 0) {
return 1;
} else if (n == k) {
return 1;
} else if (n < k) {
return 0;
} else {
return choose(n-1, k-1) + choose(n-1, k);
}
}
我的想法是在每次调用时使用三个寄存器将值存储到堆栈中 $s0, $s1, $s2，其中 $s0 将包含更新后的值 n； $s1 将保持 k 的值；并且 $s2 将在第二个 choose(n-1, k) 中保留 k 的值，因为该值只会在 parent 调用更改它时减少。我选择这个的原因是因为 k 的值没有从这个调用中的每个调用中减去，它应该是相同的，直到 parent 在上一个调用中递减它。
这是我正在尝试执行的 Choose 程序。当然，问题是我没有得到正确答案。
Choose:
#store current values onto stack
addi $sp, $sp, -16
sw $ra, 0($sp)
sw $s0, 4($sp)
sw $s1, 8($sp)
sw $s2, 12($sp)
#check values meet criteria to add to $v0
beq $s1, [=11=], one
beq $s0, $s1, one
blt $s0, $s1, zero
beq $s2, [=11=], one
#no branches passed so decrement values of n and k
subi $s0, $s0, 1
subi $s1, $s1, 1
#move values of registers to $a's for argument passing
move $a0, $s0
move $a1, $s1
jal Choose #call procedure again
#this is where I'm having my problems
#not sure how to loop the procedure to get
#the second half of the equation Choose(n-1,k)
#which is the reason for the next 2 lines of code
move $a2, $s2
jal Choose
add $v0, $v0, $v1
j Choose_Exit
#add one to $v1 from branch passed
one:
addi $v1, $v1, 1
j Choose_Exit
#branch returns 0
zero:
addi $v1, $v1, 0
j Choose_Exit
#return values to caller from stack
Choose_Exit:
lw $s2, 12($sp)
lw $s1, 8($sp)
lw $s0, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 16
jr $ra
所以我在理解如何正确实施此递归过程两次以将它们加在一起时遇到问题。我可以理解如何在 MIPS 中创建递归过程来执行阶乘，因为这始终是任何语言的递归定义。但是使用带有不同参数的递归，然后将它们全部加在一起，这让我很困惑。
当写在纸上时，我了解到这个程序可以用 parent 和 children 的二叉树来表示。 parent 是单个函数 Choose(n,k)，children 是 Choose(n-1, k-1) + Choose(n-1, k)，一旦 if 语句的叶子 children 分支之一，它将一个数字传递给 parent，后者将等待其他被调用者部分添加到 return 其值，等等等等。
任何帮助我指出我的方法做错了什么的正确方向都会很棒。我理解开头，我理解结尾，只需要一些帮助来帮助理解中间最重要的部分。
你们很接近。
您为 return 地址、arg1、arg2 建立了堆栈框架，并保存了 return 值。
您的主要障碍是，在第一次调用您的函数后，您必须将 $v0 保存到堆栈上 [如玛格丽特上面提到的]。
这是一些我认为可以使用的代码。它与您的非常相似，但我是从头开始编写的。它具有第一个调用的 return 值的正确 "push"/"pop"。
我确实为早期逃逸 [non-recursive] 案例添加了一个小优化：它们省略了创建堆栈帧。
无论如何，这里是：
#@+
# int
# choose(int n, int k)
# {
#
# if (k == 0)
# return 1;
#
# if (n == k)
# return 1;
#
# if (n < k)
# return 0;
#
# return choose(n - 1,k - 1) + choose(n - 1,k);
# }
#@-
.text
# choose -- choose
#
# RETURNS:
# v0 -- return value
#
# arguments:
# a0 -- n
# a1 -- k
#
# registers:
# t0 -- temp for 1st return value
choose:
beqz $a1,choose_one # k == 0? if yes, fly
beq $a0,$a1,choose_one # n == k? if yes, fly
blt $a0,$a1,choose_zero # n < k? if yes, fly
# establish stack frame (preserve ra/a0/a1 + space for v0)
sub $sp,$sp,16
sw $ra,12($sp)
sw $a0,8($sp)
sw $a1,4($sp)
addi $a0,$a0,-1 # get n - 1 (common to both calls)
# choose(n - 1,k - 1)
addi $a1,$a1,-1 # get k - 1
jal choose
sw $v0,0($sp) # save 1st return value (on _stack_)
# choose(n - 1,k)
addi $a1,$a1,1 # get k (from k - 1)
jal choose
lw $t0,0($sp) # "pop" first return value from stack
add $v0,$t0,$v0 # sum 1st and 2nd values
# restore from stack frame
lw $ra,12($sp)
lw $a0,8($sp)
lw $a1,4($sp)
add $sp,$sp,16
jr $ra # return
choose_one:
li $v0,1
jr $ra
choose_zero:
li $v0,0
jr $ra
更新：
First off, I like how you noted the procedure as you did before you called it. I'm going to steal that!
请客！它来自多年编写asm。有关如何写好 asm 的初步想法，请参阅我的回答：
I've tried this and it works. I need to experiment with your code to understand why the stack is manipulated when it is (always thought it had to be at the very beginning and end of a proc).
通常，栈帧是在proc开始时建立并在proc结束时恢复。基于已经建立的框架，您处理 "quick escape" [non-recursive] 案例的代码 是 正确的。
这只是一个小的优化。但是，这是因为 mips 有如此多的寄存器，对于小函数，我们甚至不需要堆栈帧，特别是如果函数是 "leaf" 或 "tail"（即它不调用任何其他函数）。
对于较小的 [non-recursive] 函数，有时我们可以使用仅保留 $ra 的单字堆栈框架（例如）：fncA 调用 fncB , 但 fncB 是一片叶子。 fncA 需要框架，但 fncB 不需要 。事实上，如果我们控制这两个功能并且我们知道 fncB 不会修改给定的临时寄存器（例如$t9), 我们可以在那里保存 return 地址而不是在 fncA:
fncA:
move $t9,$ra # preserve return address
jal fncB # call fncB
jr $t9 # return
fncB:
# do stuff ...
jr $ra # return
通常，我们不能依赖 fncB 保留 $t9，因为根据 mips ABI，fncB 可以自由 modify/trash 任何寄存器是不是$sp或$s0-$s7。但是，如果我们精心设计函数，使我们认为 fncB 是 "private" 到 fncA（例如，像 C static 函数，只有 fncA 可以访问), 我们可以随心所欲。
信不信由你，fncA 以上 是 ABI 符合。
给定的 被调用者（例如 fncA）不需要 $ra [为了[缘故] of] 它的 来电者 ，只是为了它自己。而且，重要的是$ra里面的值，而不是具体的寄存器。被调用者只需要保留 $s0-$s7，确保 $sp 在退出时具有与入口相同的值，并且它 return 到调用者中的正确地址 [jr $t9 确实如此——因为它有 值 ，当 fncA 被调用时，它在 $ra 中。
I like your use of the temp register.
需要一个额外的寄存器，因为在 mips 中，我们可以不能从内存操作数进行算术运算。 mips 只能做 lw/sw。 （即）没有这样的东西：
add $v0,$v0,0($sp)
我将 $t0 用于 simplicity/clarity，因为当您需要临时调节器时，通常使用 $t0-$t9。使用$t0时的代码"reads better"。但是，这只是一个约定。
在mips ABI中，$a0-$a3可以修改，$v1也可以修改，只需要保留$s0-$s7。并且，"modification" 意味着它们可以用来保存任何值或用于任何目的。
在上面的link中，注意strlen递增$a0直接找到字符串的结尾。它使用 $a0 是为了一个有用的目的，但是，就调用者而言，$a0 被 strlen "trashed"。这种用法是 ABI conforming.
在 choose 中，我几乎可以使用 任何 寄存器：$v1、$a2-$a3 而不是 $t0。事实上，在 choose 中的那个特定点，不再需要 $a0，因此它可以用来代替 $t0。尽管对于 choose，我们 非 -ABI 符合（因为我们 save/restore $a0-$a1），这在 choose 中是可行的，因为我们从函数 epilog [stack frame pop] 恢复 $a0 的原始值，保留函数的递归性质。
正如我所说，$t0-$t9 是用于 scratch space 的常用寄存器。但是，我已经编写了使用所有 10 个函数的函数，并且仍然需要更多（例如，使用 Bresenham 圆算法绘制到帧缓冲区中）。 $v0-$v1 和 $a0-$a3 可以用作临时寄存器以获得额外的 6。如有必要，$s0-$s7 可以保留在堆栈帧中，只是为了释放它们以用作更多临时寄存器.
免责声明：我重写了汇编代码没有检查它。
- 有一些延迟槽需要考虑，这样可以更好地巧妙地使用它们并使其显式化，以避免在分支指令之后聚合隐式 nop 指令。
- 颠倒 choose(n - 1,k - 1) 和 choose(n - 1,k) 之间的调用顺序，以便更智能地使用 $a0 和 $a1 以及堆栈。
- 限制仅调用 choose(n - 1,k) 的堆栈使用，并使用尾调用调用 choose(n - 1,k - 1)。
- 堆叠a0-1而不是a0的值更有意义。
- 我们将所有内容累加到 $v0 中，而不是堆叠它。我们将 $t0 作为本地结果添加到 $v0 中，因为它很便宜，而我们可以通过直接使用 $v0 来丢弃它。
- 因此，总体变化应该使 icache 更快乐地使用更少的指令，并使 dcache 更快乐地使用更少的堆栈 space。
汇编代码：
#@+
# int
# choose(int n, int k)
# {
#
# if (k == 0)
# return 1;
#
# if (n == k)
# return 1;
#
# if (n < k)
# return 0;
#
# return choose(n - 1,k - 1) + choose(n - 1,k);
# }
#@-
.text
# choose -- choose
#
# RETURNS:
# v0 -- return value
#
# arguments:
# a0 -- n
# a1 -- k
#
# registers:
# t0 -- temp for local result to accumulate into v0
choose:
j choose_rec
addui $v0, $zr, 0 # initialize $v0 to 0 before calling
choose_rec:
beqz $a1,choose_one # k == 0? if yes, fly
addui $t0,$zr,1 # branch delay-slot with $t0 = 1
beq $a0,$a1,choose_one # n == k? if yes, fly
nop # branch delay-slot with $t0 = 1 already done
blt $a0,$a1,choose_zero # n < k? if yes, fly
addui $t0,$zr,0 # branch delay-slot with $t0 = 0
# establish stack frame (preserve ra/a0/a1)
sub $sp,$sp,12
addui $a0,$a0,-1 # get n - 1 (common to both calls)
sw $ra,8($sp)
sw $a0,4($sp)
jal choose_rec # choose(n - 1,k)
sw $a1,0($sp)
# restore from stack frame
lw $ra,8($sp)
lw $a0,4($sp)
lw $a1,0($sp)
add $sp,$sp,12
# choose(n - 1,k - 1)
j choose_rec # tail call: jump instead of call
addi $a1,$a1,-1 # get k - 1
choose_one:
choose_zero:
jr $ra # return
addui $v0,$v0,$t0 # branch delay-slot with $v0 += $t0