使用 MIPS 的双重递归
Double recursion using MIPS
我正在尝试为函数 f(n) = 2f(n-1) + 3f(n-2) + 1 实现双重递归。我能够弄清楚奇异递归并实现它的 2f(n-1) + 1 部分，但我不知道如何实现第二部分。这是我的奇异递归工作代码：
.data
prompt1: .asciiz "Enter the value for the recursive function f(n) = 2f(n-1)+3f(n-2)+1: "
prompt2: .asciiz "Result: "
numberEntered: .word 0
answer: .word 0
.text
main:
#Ask for the value
li $v0 4
la $a0, prompt1
syscall
#enter value
li $v0, 5
syscall
sw $v0, numberEntered #stores the number
# call the function
lw $a0, numberEntered
jal function
sw $v0, answer
#Print out the result
li $v0 4
la $a0, prompt2
syscall
lw $a0, answer
li $v0, 1
syscall
li $v0, 10
syscall
.globl function
function:
subu $sp, $sp, 8
sw $ra, ($sp)
sw $s0, 4($sp)
#base case
li $v0, 1
beq $a0, $zero, done
#calling f(n-1)
move $s0, $a0
sub $a0, $a0, 1
jal function
#calculations occur here
mul $v0, $v0, 2
addi $v0, $v0, 1
done:
lw $ra, ($sp)
lw $s0, 4($sp)
addi $sp, $sp, 8
jr $ra #returns
我尝试在它的计算部分将下一部分的地址加载到堆栈中，但我无法找出实现它的方法。我必须 "wind up" 堆栈两次吗？一旦它是当前和曾经在计算部分？我想不通，如有任何帮助，我们将不胜感激！
相当不错。
回答你的问题：你可以简单地在 function 入口处建立一个堆栈框架，并在最后从它恢复。
我确实不得不稍微改变 $s0 的用途以存储中间值并将其添加到堆栈框架中的存储值（即堆栈框架现在是 3 个单词而不是 2 个）。
无论如何，这是更正后的代码。我试着给它加了一点注释（IMO，在 asm 中，没有 "too many comments" 这样的东西）[请原谅不必要的样式清理]:
.data
prompt1: .asciiz "Enter the value for the recursive function f(n) = 2f(n-1)+3f(n-2)+1: "
prompt2: .asciiz "Result: "
numberEntered: .word 0
answer: .word 0
.text
main:
# Ask for the value
li $v0,4
la $a0,prompt1
syscall
# enter value
li $v0,5
syscall
sw $v0,numberEntered # stores the number
# call the function
lw $a0,numberEntered
jal function
sw $v0,answer
# Print out the result
li $v0,4
la $a0,prompt2
syscall
lw $a0,answer
li $v0,1
syscall
li $v0,10
syscall
.globl function
# function -- calculation
# v0 -- return value
# a0 -- current n value
# s0 -- intermediate result
function:
subi $sp,$sp,12 # establish our stack frame
sw $ra,8($sp) # save return address
sw $a0,4($sp) # save n
sw $s0,0($sp) # save intermediate result
# base case
# NOTE: with the addition of n-2, the "beq" was insufficient
li $v0,1
ble $a0,$zero,done
# calling f(n-1)
sub $a0,$a0,1 # get n-1
jal function
# NOTE: these could be combined into a single instruction
mul $v0,$v0,2 # get 2f(n-1)
move $s0,$v0 # save it
# calling f(n-2)
sub $a0,$a0,1 # get n-2
jal function
mul $v0,$v0,3 # get 3f(n-2)
# get 2f(n-1) + 3f(n-2) + 1
add $v0,$s0,$v0
add $v0,$v0,1
done:
lw $ra,8($sp) # restore return address
lw $a0,4($sp) # restore n
lw $s0,0($sp) # restore intermediate result
addi $sp,$sp,12 # pop stack frame
jr $ra # returns
更新：
This solution is way simpler than I thought it would be.
这可能是因为堆栈帧在 asm [或 C] 中完成的方式。
考虑一个现代 C 程序：
int
whatever(int n)
{
int x;
// point A
x = other(1);
// do lots more stuff ...
{
// point B
int y = other(2);
// do lots more stuff ...
// point C
n *= (x + y);
}
// do lots more stuff ...
n += ...;
return n;
}
C 编译器将在进入 whatever 时建立一个栈帧，为 x 保留 space and y 尽管 y 只是 set 很久以后。大多数 C 程序员没有意识到这一点。
在解释性语言中（例如 java、python 等）space 对于 y 不保留 直到 point B 处的代码 已执行 。而且，当 y 变为 "out of scope" [point C] 后
时，他们 [通常] 会释放它。
大多数 C 程序员认为具有作用域的声明[如y]可以节省堆栈space。 （即）在范围块中，编译器将增加堆栈帧大小以容纳 y 并在不再需要 y 时再次缩小它。
这简直不正确。 C 编译器将为 all 函数范围变量设置堆栈帧并保留 space，即使它们在函数后期或内部范围内声明[如 y].
这正是我们在您的 function 中所做的。这是真的，即使我们没有 need/utilize 堆栈 space [在偏移量 0] for $s0 直到函数的中间。
所以，我猜你使用其他语言的经验 做 动态 space 保留 space 或关于 C 的常识可能导致你您认为需要的更复杂的模型。因此，您最初的问题是：我必须 "wind up" 堆栈两次吗？
我还应该提到 function 的调用约定 不符合 ABI。如果它是独立的（即不调用任何其他东西），这 完美 很好。也就是说，在 asm 中，对于 "leaf" 函数，我们可以随意定义。
原因是$a0被被叫者呼叫modified/trashed。我们从堆栈中 saved/restored 它，但是调用另一个函数可能会把事情搞砸。补救办法只是使用另一个寄存器来保存值 [或 save/restore 到堆栈帧中的额外位置]，因此如果 function 最终调用其他东西，则需要更多工作。
我正在尝试为函数 f(n) = 2f(n-1) + 3f(n-2) + 1 实现双重递归。我能够弄清楚奇异递归并实现它的 2f(n-1) + 1 部分，但我不知道如何实现第二部分。这是我的奇异递归工作代码：
.data
prompt1: .asciiz "Enter the value for the recursive function f(n) = 2f(n-1)+3f(n-2)+1: "
prompt2: .asciiz "Result: "
numberEntered: .word 0
answer: .word 0
.text
main:
#Ask for the value
li $v0 4
la $a0, prompt1
syscall
#enter value
li $v0, 5
syscall
sw $v0, numberEntered #stores the number
# call the function
lw $a0, numberEntered
jal function
sw $v0, answer
#Print out the result
li $v0 4
la $a0, prompt2
syscall
lw $a0, answer
li $v0, 1
syscall
li $v0, 10
syscall
.globl function
function:
subu $sp, $sp, 8
sw $ra, ($sp)
sw $s0, 4($sp)
#base case
li $v0, 1
beq $a0, $zero, done
#calling f(n-1)
move $s0, $a0
sub $a0, $a0, 1
jal function
#calculations occur here
mul $v0, $v0, 2
addi $v0, $v0, 1
done:
lw $ra, ($sp)
lw $s0, 4($sp)
addi $sp, $sp, 8
jr $ra #returns
我尝试在它的计算部分将下一部分的地址加载到堆栈中，但我无法找出实现它的方法。我必须 "wind up" 堆栈两次吗？一旦它是当前和曾经在计算部分？我想不通，如有任何帮助，我们将不胜感激！
相当不错。
回答你的问题：你可以简单地在 function 入口处建立一个堆栈框架，并在最后从它恢复。
我确实不得不稍微改变 $s0 的用途以存储中间值并将其添加到堆栈框架中的存储值（即堆栈框架现在是 3 个单词而不是 2 个）。
无论如何，这是更正后的代码。我试着给它加了一点注释（IMO，在 asm 中，没有 "too many comments" 这样的东西）[请原谅不必要的样式清理]:
.data
prompt1: .asciiz "Enter the value for the recursive function f(n) = 2f(n-1)+3f(n-2)+1: "
prompt2: .asciiz "Result: "
numberEntered: .word 0
answer: .word 0
.text
main:
# Ask for the value
li $v0,4
la $a0,prompt1
syscall
# enter value
li $v0,5
syscall
sw $v0,numberEntered # stores the number
# call the function
lw $a0,numberEntered
jal function
sw $v0,answer
# Print out the result
li $v0,4
la $a0,prompt2
syscall
lw $a0,answer
li $v0,1
syscall
li $v0,10
syscall
.globl function
# function -- calculation
# v0 -- return value
# a0 -- current n value
# s0 -- intermediate result
function:
subi $sp,$sp,12 # establish our stack frame
sw $ra,8($sp) # save return address
sw $a0,4($sp) # save n
sw $s0,0($sp) # save intermediate result
# base case
# NOTE: with the addition of n-2, the "beq" was insufficient
li $v0,1
ble $a0,$zero,done
# calling f(n-1)
sub $a0,$a0,1 # get n-1
jal function
# NOTE: these could be combined into a single instruction
mul $v0,$v0,2 # get 2f(n-1)
move $s0,$v0 # save it
# calling f(n-2)
sub $a0,$a0,1 # get n-2
jal function
mul $v0,$v0,3 # get 3f(n-2)
# get 2f(n-1) + 3f(n-2) + 1
add $v0,$s0,$v0
add $v0,$v0,1
done:
lw $ra,8($sp) # restore return address
lw $a0,4($sp) # restore n
lw $s0,0($sp) # restore intermediate result
addi $sp,$sp,12 # pop stack frame
jr $ra # returns
更新：
This solution is way simpler than I thought it would be.
这可能是因为堆栈帧在 asm [或 C] 中完成的方式。
考虑一个现代 C 程序：
int
whatever(int n)
{
int x;
// point A
x = other(1);
// do lots more stuff ...
{
// point B
int y = other(2);
// do lots more stuff ...
// point C
n *= (x + y);
}
// do lots more stuff ...
n += ...;
return n;
}
C 编译器将在进入 whatever 时建立一个栈帧，为 x 保留 space and y 尽管 y 只是 set 很久以后。大多数 C 程序员没有意识到这一点。
在解释性语言中（例如 java、python 等）space 对于 y 不保留 直到 point B 处的代码 已执行 。而且，当 y 变为 "out of scope" [point C] 后
大多数 C 程序员认为具有作用域的声明[如y]可以节省堆栈space。 （即）在范围块中，编译器将增加堆栈帧大小以容纳 y 并在不再需要 y 时再次缩小它。
这简直不正确。 C 编译器将为 all 函数范围变量设置堆栈帧并保留 space，即使它们在函数后期或内部范围内声明[如 y].
这正是我们在您的 function 中所做的。这是真的，即使我们没有 need/utilize 堆栈 space [在偏移量 0] for $s0 直到函数的中间。
所以，我猜你使用其他语言的经验 做 动态 space 保留 space 或关于 C 的常识可能导致你您认为需要的更复杂的模型。因此，您最初的问题是：我必须 "wind up" 堆栈两次吗？
我还应该提到 function 的调用约定 不符合 ABI。如果它是独立的（即不调用任何其他东西），这 完美 很好。也就是说，在 asm 中，对于 "leaf" 函数，我们可以随意定义。
原因是$a0被被叫者呼叫modified/trashed。我们从堆栈中 saved/restored 它，但是调用另一个函数可能会把事情搞砸。补救办法只是使用另一个寄存器来保存值 [或 save/restore 到堆栈帧中的额外位置]，因此如果 function 最终调用其他东西，则需要更多工作。