1. ホーム
  2. recursion

[解決済み】MIPSアセンブリを使用した再帰的な関数

2022-02-19 03:33:20

質問

課題で困っていることがあるので、助けてほしいのですが。私は答えを求めるのではなく、2つを組み合わせて自分で解決したいのですが、MIPSについてほとんど知らないので、どこから始めればいいのかわかりません。

以下は、私が始めたことです。

.data


.text
main:

addi $sp, $sp, -16  #prepare stack for 4 items
sw $s0, 0($sp)
sw $s1, 4($sp)
sw $s2, 8($sp)
sw $ra, 12($sp)
move $s0, $a0
move $s1, $a1

add $s2, $s0, $s1   #add two previous numbers and store result in $s2

move $v0, $s2   #put answer into $v0

lw $s0, 0($sp)
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
jr$ra

基本的には、再帰関数を使ってフィボナッチ数を計算し、ループを使ってフィボナッチ数列の最初の10個をプリントアウトすることになります。

いろいろな例を調べてみましたが、どれもまだ習っていない命令を使っているので意味がわからず、使うことを想定していないとしか思えません。上のコードでは、基本的にスタックを作って、$raを3つの値、足す2つの数値と合計とともに格納しています。私の問題の一つは、関数がどこで始まり、どこで終わるのか、そして行われている作業の全体が何であるのかを理解することです。

印刷するには、次のように使うことも教えてもらいました。

li $v0, 1
move $a0, $s0
syscall

に格納されている値を表示していると考えてよいでしょうか? $v0 ?

解決方法は?

ここに、あなたの関数のコードがあります。答えを求めているわけではないのでしょうが、時には例を探して、それがどのように動作するかを見ることで、それが実際にどのように動作するかを理解するポイントに容易に到達することができます。

.data
msg1: .asciiz "Give a number: "

.text
.globl main
main:
    li $v0,  4
    la $a0,  msg1
    syscall             # print msg
    li $v0,  5
    syscall             # read an int
    add $a0, $v0, $zero # move to $a0

    jal fib             # call fib

    add $a0, $v0, $zero
    li  $v0, 1
    syscall

    li $v0, 10
    syscall

fib:
    # $a0 = y
    # if (y == 0) return 0;
    # if (y == 1) return 1;
    # return fib(y - 1) + fib(y - 2);

    #save in stack
    addi $sp, $sp, -12 
    sw   $ra, 0($sp)
    sw   $s0, 4($sp)
    sw   $s1, 8($sp)

    add $s0, $a0, $zero

    addi $t1, $zero, 1
    beq  $s0, $zero, return0
    beq  $s0, $t1,   return1

    addi $a0, $s0, -1

    jal fib

    add $s1, $zero, $v0         # $s1 = fib(y - 1)

    addi $a0, $s0, -2

    jal fib                     # $v0 = fib(n - 2)

    add $v0, $v0, $s1           # $v0 = fib(n - 2) + $s1

    exitfib:

        lw   $ra, 0($sp)        # read registers from stack
        lw   $s0, 4($sp)
        lw   $s1, 8($sp)
        addi $sp, $sp, 12       # bring back stack pointer
        jr $ra

    return1:
        li $v0,1
        j exitfib

    return0:     
        li $v0,0
        j exitfib

Gusbroが言ったように、mipsで再帰を使うには、2つのことをしなければなりません。 jal (ジャンプとリンク)で関数名を指定しますが、最初に必ずリターンアドレスをスタックに格納します。 $ra そうすれば、将来、最初に戻りたいときには jr $ra . リターンアドレスが保存されていない状態で jr が表示される可能性が高いです。 invalid program counter error .