MIPS 递归字符串长度？

Question

我目前正在尝试实现一个递归函数来计算 MIPS 中字符串的长度。这是我现在拥有的代码。我正在努力找出基本情况以及如何使其达到 return 字符串长度。我觉得我非常接近，因为当我逐步执行该程序时，它会正确计算并存储输入的字符串的长度。感谢任何帮助：

.text
#.align 2


main:
la $a0, input #load string for user input
li $v0, 4 #command to print string in syscall
syscall 

li $v0, 8 #command to take user input 
la $a0, buffer #store string of user input in buffer
li $a1,256 #length of buffer for string
    syscall


move $t0,$a0 #move string address to $t0

addi $t2,$t2,0 #initialize word length counter

addi $sp, $sp, -16 #allocate space in stack
sw $t0,16($sp) #store string address in stack, which will be the working string 
    sw $ra,12($sp) #save return address 
    sw $t2,8($sp) #save word length counter
    jal reclength


    # if we get here then the string is finished 

reclength:
    lw $t0,16($sp) #load word from stack and store address in $t0
    lw $t1,8($sp) #load counter from stack and store in $t1
    lbu $t2,0($t0) #get first bit from word in position 0 of address stored in $t0

    ## BASE CASE ##
    beq $t2,$zero,finisher

    ## RECURSIVE CASE ##
    addi $t1,$t1,1 #incremement length counter
    addi $t0,$t0,1 #point to the next character

    addi $sp, $sp, -16
    sw $t1,8($sp) #store the counter in the stack
    sw $ra,12($sp) #store the return address in the stack
    sw $t0,16($sp) #store new address in stack
    jal reclength



    #jr $ra
    #nop


finisher:
lw $t1,8($sp) #load counter from stack
addi $t1,$t1,-1 #decrement counter because null counter was counted
la $a0, ending #load string for user input
    li $v0, 4 #command to print string in syscall
    syscall 
jr $ra







.data
#.align 2
input:   .asciiz "Enter a string : " 
buffer:  .space 256
ending:  .asciiz "Finished"

Answer 1

您为每个函数调用不断移动堆栈指针 "downward"，但您从不向上调整它 return。

我发现在堆栈上具有 return 值的整个设计有点奇怪。通常人们会使用 $v0 到 return 函数的值。所以我会像这样重写函数：

reclength:
    lw $t0,12($sp)  # load string address from stack and place it in $t0
    lbu $t2,0($t0)  # read one byte from the string and place it in $t2

    bne $t2,$zero,recurse
    li $v0, 0       # base case : length = 0
    j return

recurse:
    # recursive case : return reclength(addr+1) + 1
    addi $t0,$t0,1 # point to the next character

    addi $sp, $sp, -16
    sw $ra,8($sp)  # store the return address in the stack
    sw $t0,12($sp) # store new address in stack
    jal reclength
    addi $v0,$v0,1 

return:
    lw $ra, 8($sp)  # restore the return address
    addiu $sp,$sp,16 # restore the stack pointer
    jr $ra

你会这样称呼：

addi $sp, $sp, -16 #allocate space in stack
sw $t0,12($sp) #store string address in stack, which will be the working string 
sw $ra,8($sp) #save return address 
jal reclength

您也可以去掉堆栈上的字符串地址，而改用 $a0。但我会把它留给你作为练习。

您可能还想在 reclength return 到 main 后正确退出程序：

li $v0,10  # syscall 10 = exit
syscall

MIPS 递归字符串长度？

MIPS Recursive String Length?

assembly

mips