MIPS递归字符串长度？ [英] MIPS Recursive String Length?

问题描述

我目前正在尝试实现一个递归函数来计算以MIPS为单位的字符串长度。这是我现在掌握的代码。我正在努力弄清楚基本情况以及如何让它返回字符串长度。我觉得我非常接近，因为当我单步执行程序时，它会正确地计算并存储输入的字符串的长度。如有任何帮助，我们不胜感激：

.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"

推荐答案

对于您进行的每个函数调用，您都会将堆栈指针"下移"，但从未在返回时向上调整它。

我发现将返回值放在堆栈上的整个设计有点奇怪。通常使用$v0返回函数的值。所以我会重写函数，如下所示：

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返回到main：

后正确退出程序

li $v0,10  # syscall 10 = exit
syscall

这篇关于MIPS递归字符串长度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！