recursion - 使用 MIPS 的双递归

Question

我正在尝试为函数 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

我尝试在它的计算部分将下一部分的地址加载到堆栈中，但我无法弄清楚使其工作的实现。我是否必须两次“结束”堆栈？一次是当前如何，一次是在计算部分？我无法弄清楚，任何帮助将不胜感激!

Answer 1

相当不错的努力。

回答你的问题:你可以简单地在 function 建立一个堆栈框架最后进入并从中恢复。

我确实必须重新调整用途 $s0稍微存储一个中间值并将其添加到堆栈帧中的存储值(即堆栈帧现在是 3 个字而不是 2 个)。

无论如何，这是更正后的代码。我试图对其进行一些注释(IMO，在 asm 中，没有“评论太多”这样的东西)[请原谅无偿的风格清理]:

    .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 保留空间和 y即使 y只是在很晚之后才设置。大多数 C 程序员没有意识到这一点。

在解释型语言(例如 java 、 python 等)中， y 的空间直到 point B 处的代码才保留被执行。而且，他们 [通常] 会在 y 时解除分配它进入“超出范围”[之后 point C ]。

大多数 C 程序员认为有一个作用域声明 [如 y ] 节省堆栈空间。 (即)在作用域块中，编译器将增加堆栈帧大小以适应 y并在 y 时再次收缩它不再需要。

这是不正确的。 C 编译器将为所有函数作用域变量设置堆栈帧并保留空间，即使它们是在函数的后期或内部作用域内声明的 [如 y ]。

这正是我们在您的 function 中所做的.即使我们不需要/使用 $s0 的堆栈空间 [at offset 0] 也是如此。直到函数的中间。

因此，我猜测您使用其他动态[有效] 保留空间的语言的经验或有关 C 的常识可能使您对您认为需要的内容产生了更复杂的模型。因此，您最初的问题是:我是否必须两次“结束”堆栈？

我还应该提到 function 的调用约定不符合 ABI。如果它是自包含的(即不调用其他任何东西)，这是完全没问题的。也就是说，在 asm 中，对于“叶”函数，我们可以定义任何我们想要的。

原因是$a0调用被被调用者修改/删除。我们从堆栈中保存/恢复了它，但是调用另一个函数可能会把事情搞砸。补救措施只是使用另一个寄存器来保存值[或保存/恢复到堆栈帧中的额外位置]，因此如果 function 需要做更多的工作。最终调用别的东西。