使用MIPS进行双重递归 [英] Double recursion using MIPS

问题描述

我正在尝试对函数f(n) = 2f(n-1) + 3f(n-2) + 1实现双重递归.我能够找出奇异的递归并实现它的2f(n-1) + 1部分，但是我无法弄清楚如何实现第二部分.这是我的奇异递归的工作代码:

I am trying to implement double recursion for the function f(n) = 2f(n-1) + 3f(n-2) + 1. I was able to figure out singular recursion and implement the 2f(n-1) + 1 part of it, but I can't figure out how to implement the second part. Here is my working code for the singular recursion:

.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

我尝试将下一部分的地址加载到其计算部分的堆栈中，但是我无法弄清楚实现该功能的实现.我是否必须结束"堆栈两次?一次是当前情况如何，一次是在计算部分中?我不明白，任何帮助将不胜感激！

I tried loading the address of the next part down the stack in the calculation part of it, but I couldn't figure out the implementation to get it to work. Do I have to "wind up" the stack twice? Once how it is currently and once in the calculation section? I can't figure it out, and any help would be appreciated!

推荐答案

相当努力.

要回答您的问题:您只需在function条目处建立一个堆栈框架，然后从其末尾恢复即可.

To answer your question: you can simply establish a stack frame at function entry and restore from it at the end.

我确实不得不稍微调整$s0的用途来存储中间值，并将其添加到堆栈帧中的已存储值中(即，堆栈帧现在是3个单词，而不是2个单词).

I did have to repurpose $s0 slightly to store an intermediate value and add it to the stored values in the stack frame (i.e. stack frame is now 3 words instead of 2).

无论如何，这是正确的代码.我尝试对其进行注释( IMO，在asm中，没有注释太多" 这样的东西)[请原谅免费的样式清理]:

Anyway, here's the corrected code. I've tried to annotate it a bit (IMO, in asm, there's no such thing as "too many comments") [please pardon the gratuitous style cleanup]:

    .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]中完成堆栈框架的方式.

That may be because of the way a stack frame is done in asm [or C].

考虑一个现代的C程序:

Consider a modern C program:

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 set 之后.大多数C程序员都没有意识到这一点.

The C compiler will establish a stack frame upon entry to whatever that will reserve space for x and y even though y is only set much later. Most C programmers don't realize this.

在解释语言(例如，java，python等)中，y的空间未保留直到，point B处的代码已被执行 >.而且，当y超出范围" [在point C]之后时，它们通常会[取消分配].

In interpreted languages (e.g. java, python, etc.) space for y isn't reserved until the code at point B is executed. And, they will [usually] deallocate it when y goes "out of scope" [after point C].

大多数C程序员 都认为具有范围界定的声明(如y)可以节省堆栈空间. (即)在作用域块中，编译器将增加堆栈帧大小以适应y，并在不再需要y时再次缩小它.

Most C programmers think that having a scoped declaration [like y] saves on stack space. (i.e.) In the scoped block, the compiler would increase the stack frame size to accomodate y and shrink it again when y is no longer needed.

这完全是不正确的. C编译器将为所有 all 函数范围的变量设置堆栈框架并保留空间，即使它们是在函数后期或内部范围内声明的也是如此[如y].

This is simply not correct. The C compiler will set up the stack frame and reserve space for all function scoped variables even if they're declared late in the function or inside an inner scope [like y].

这就是我们在您的function中所做的.即使我们直到函数中间都不需要/利用$s0的堆栈空间[偏移量为0]，这也是正确的.

This is just what we did in your function. This is true even though we didn't need/utilize the stack space [at offset 0] for $s0 until the middle of the function.

所以，我猜测您使用其他确实语言有效[有效地]保留空间的经验，或者关于C的常识可能使您建立了一个更加复杂的模型，即您认为必需的.因此，您的原始问题是:我是否必须结束"堆栈两次?

So, I'm guessing that your experiences with other languages that do reserve space dynamically [effectively] or the common wisdom about C may have led you to a more complex model of what you thought was required. Hence your original question: Do I have to "wind up" the stack twice?

我还应该提到function的调用约定不符合 ABI.如果它是自包含的，则完全是可以的(即不调用其他任何东西).也就是说，在asm中，对于叶子"功能，我们可以定义所需的内容.

I should also mention that the calling convention of function is not ABI conforming. This is perfectly fine if it's self contained (i.e. does not call anything else). That is, in asm, for "leaf" functions, we can define whatever we wish.

原因是被呼叫者修改/处理了$a0呼叫.我们从堆栈中保存/恢复了它，但是调用另一个函数可能会使事情搞砸.补救措施就是简单地使用另一个寄存器来保存值[或保存/恢复到堆栈帧中的其他位置]，因此如果function最终调用了其他内容，则需要做更多的工作.

The reason is that $a0 call be modified/trashed by callee. We saved/restored it from the stack, but calling another function might mess things up. The remedy would simply be to use another register to preserve the value [or save/restore to an extra place in the stack frame], so a bit more work if function ends up calling something else.

这篇关于使用MIPS进行双重递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！