MIPS 双重递归问题“无法将堆栈段扩展 16 字节至 524288 字节”

Question

我正在尝试使用遵循以下伪代码的 MIPS 实现双重递归程序：

procedure DRAGON(order, sign)
    if order = 0 then
        Move forward
    else
        DRAGON(order-1; 1)
        Turn 90sign
        DRAGON(order-1; -1)

这是我到目前为止所拥有的，但是当我运行它时，我得到了这个错误：

Can't expand stack segment by 16 bytes to 524288 bytes.
Use -lstack # with # > 524288

我是 MIPS 的新手，所以我很难调试它。我怀疑这可能是因为我正在进行无限递归调用，但我不确定如何解决这个问题。谁能帮忙指出问题所在？

        .data
# SVG path segment commands
up:     .asciiz "v-5"
right:  .asciiz "h5"
down:   .asciiz "v5"
left:   .asciiz "h-5"

# Print one of the path segment strings by readings its address
# from this array of pointers
        .align 2
dirs:   .word up, right, down, left

# Keep the current direction (0-3) in this single byte value
direction:
        .byte 3

        .text
        # $a0 = order (an unsigned integer)
        # $a1 = sign (either 1 or -1)

        .globl dragon

dragon:
        addiu   $sp, $sp, -16           # allocate space on stack (multiple of 8)
        la      $t0, dirs               # t0: dirs array address
        lbu     $t1, direction          # t1: load current direction byte
        move    $t6, $t1                # t6: copy of current direction byte
        li      $t2, 1                  # t2: load constant 1
        li      $t3, -1                 # t3: load constant -1

        sw      $ra, 0($sp)
        sw      $a0, 4($sp)
        sw      $a1, 8($sp)
        beq     $a0, [=12=], base

        move    $t4, $a1                # t4: keep current sign (1 or -1)
        addiu   $a0, $a0, -1            # order = order - 1
        move    $a1, $t2                # sign = 1
        jal     dragon                  # dragon(order-1, 1)

        li      $v0, print_int
        move    $a0, $a1
        syscall

        addu    $t5, $t6, $t4
        addiu   $t5, $t5, 4
        div     $t5, $t5, 4
        mfhi    $t6                     # t1: (direction + sign + 4) % 4 -> new direction
        sb      $t6, direction

        move    $a1, $t3
        jal     dragon                  # dragon(order-1, -1)
        j       done

base:                                   # when order = 0
        addu    $t1, $t1, $t1
        addu    $t1, $t1, $t1           # direction * 4
        addu    $t5, $t1, $t0           # base address + offset
        lw      $t5, 0($t5)             # t5: direction from array dirs

        li      $v0, print_string
        move    $a0, $t5
        syscall                         # print direction

done:
        lw      $ra, 0($sp)
        lw      $a0, 4($sp)
        lw      $a1, 8($sp)
        addiu   $sp, $sp, 16
        jr      $ra
#
# Main program
#
        .data
svg_header:
        .asciiz "<svg xmlns=\"http://www.w3.org/2000/svg\">\n"
svg_footer:
        .asciiz "</svg>\n"
path_header:
        .asciiz "<path stroke=\"black\" fill=\"none\" d=\"M225 225"
path_footer:
        .asciiz "\" />\n"

        .text

        .globl main
main:
        move    $s0, $ra

        la      $a0, svg_header
        li      $v0, print_string
        syscall

        la      $a0, path_header
        syscall

        li      $a0, 3   # Order
        li      $a1, 1   # Sign
        jal     dragon

        la      $a0, path_footer
        li      $v0, print_string
        syscall

        la      $a0, svg_footer
        syscall

        li      $v0, 10
        syscall

Answer 1

在您的递归片段中，您没有 return 在 base 位之前。因此，在第二个 jal dragon 之后，您的代码会落入基本场景，这对任何帐户来说都是错误的。到那时，t1 不再包含 direction 变量 - 它已乘以四。在 base 中，代码尝试解析 t1 ，就好像它仍然是 direction 和错误一样。

MIPS 双重递归问题“无法将堆栈段扩展 16 字节至 524288 字节”

MIPS Double Recursion Problem " Can't expand stack segment by 16 bytes to 524288 bytes"

assembly

mips

qtspim