MIPS帮助：递归函数 [英] MIPS Help: Recursive Functions
问题描述
我想code这个递归函数到MIPS。
我的问题是我不知道我该怎么办的递归步骤。结果
我是pretty确保我得到了休息是正确的。
INT复发（INT N）{
如果（N == 1 ||ñ== 2）{
返回2;
}其他{
回报（正 - 4）+ N *复发（N-2）;
}
}
。数据promptMessage：.asciiz输入一个数字是大于或等于0：
resultMessage：.asciiz\\ n此回答是：
输入：.word 0
回答：0 .word。文本
.globl主主要：
从用户＃阅读数
李$ V0，4
LA $ A0，promptMessage
系统调用李$ V0，5
系统调用SW $ V0，输入#CALL功能
LW $ A0，输入
日航复发
SW $ V0，答案#Display结果
李$ V0，4
LA $ A0，resultMessage
系统调用李$ V0，1
LW $ A0，答案
系统调用.globl复发复发：
阿迪$ SP，SP $，-8
SW $ A0，0（$ SP）
SW $ RA，4（$ SP）#Base情况下，如果（N == 0 ||ñ== 1）返回2;
李$ V0，2
BEQ $ A0，$零，DONE
BEQ $ A0，1，DONE#RECURSIVE STEP
阿迪$ A0，$ A0，-2
日航复发
您做的非常出色。首先创建C $ C $℃。你是非常接近的。
我不得不添加的计算步骤和功能收尾code。
此外，还有那里的主要打印的号码后，出现了一个错误的没有的系统调用10（退出），这样code只会落空和无限递归。
我修改了C $ C $ç稍微所以这将是与MIPS code更兼容。
只是为了好玩，并便于测试，我直到它得到一个负数改变主循环并重新提示。
我已经清理并测试了code，补充注释[请原谅无偿风格清理]：
。数据＃注意：这应首先出现，以保持对齐到4字节边界
＃（或.align伪4将做到这一点），否则，LW / SW运营人员可以在一个失败
＃对齐异常
.align伪4
输入：.word 0
回答：0 .wordpromptMessage：.asciiz输入一个数字，大于或等于0（-1停止）：
resultMessage：.asciiz\\ n此回答是：
NL：.asciiz\\ n 的.text .globl主要：
＃ 用户提示
李$ v0,4
LA $ A0，promptMessage
系统调用 ＃从用户阅读次数
李$ v0,5
系统调用
SW $ V0，输入 ＃负值意味着停止
＃注：此添加
bltz $ V0，main_exit ＃调用函数
LW $ A0，输入
日航复发
SW $ V0，答案 ＃显示结果消息
李$ v0,4
LA $ A0，resultMessage
系统调用 ＃显示编号
李$ v0,1
LW $ A0，答案
系统调用 ＃输出换行符
李$ v0,4
LA $ A0，NL
系统调用 ＃注意：这是添加到允许多次尝试，但没有它，有
＃下面的bug
J主 ＃BUG：系统调用来这里退出是_missing_等得了fallthrough为复发
＃导致堆栈溢出
main_exit：
李$ v0,10
系统调用 .globl复发＃复发 - 递归
＃
＃参数：
＃A0 - 在N的价值
＃
＃伪code：
＃* INT
＃*易复发（INT N）
＃* {
＃* INT R;
＃*
＃*如果（N == 1 ||ñ== 2）{
＃*回报2;
＃*}
＃*
＃* R =复发（N - 2）;
＃*
＃*回报（N - 4）+（N * R）;
＃*}
复发：
阿迪$ SP，SP $，-8
SW $ a0,0（$ SP）
SW $ RA，4（$ SP） ＃基本情况，如果（N == 0 ||ñ== 1）返回2;
李$ v0,2
BEQ $ A0，$零，recur_done
BEQ $ a0,1，recur_done ＃递归步骤
阿迪$ A0，$ A0，-2＃N - = 2
日航复发
我们需要LW $ a0,0（$ SP）＃N背（否（N - 2）） ＃注：此计算失踪
MUL $ V0，V0 $，$ A0＃R * = N（即（N * R））
阿迪$ A0，$ A0，-4＃N - = 4（即（N - 4））
加$ V0，V0 $，$＃A0他们总结 ＃注意：这是这个函数的栈序言标准逆转
recur_done：
LW $ a0,0（$ SP）
LW $ RA，4（$ SP）
阿迪$ SP，SP $ 8
JR $ RA
I'm trying to code this recursive function into MIPS.
My problem is I'm not sure how I can do the recursive step.
I'm pretty sure I got the rest correct.
int recur(int n) {
if(n == 1 || n == 2) {
return 2;
} else {
return (n-4)+n*recur(n-2);
}
}
.data
promptMessage: .asciiz "Enter a number that is greater than or equal to 0: "
resultMessage: .asciiz "\nThe answer is: "
input: .word 0
answer: .word 0
.text
.globl main
main:
#Read the number from the user
li $v0, 4
la $a0, promptMessage
syscall
li $v0, 5
syscall
sw $v0, input
#Call the function
lw $a0, input
jal recur
sw $v0, answer
#Display result
li $v0, 4
la $a0, resultMessage
syscall
li $v0, 1
lw $a0, answer
syscall
.globl recur
recur:
addi $sp, $sp, -8
sw $a0, 0($sp)
sw $ra, 4($sp)
#Base Case if(n == 0 || n == 1) return 2;
li $v0, 2
beq $a0, $zero, DONE
beq $a0, 1, DONE
#RECURSIVE STEP
addi $a0, $a0, -2
jal recur
You did a great job. Creating C code first. You were very close.
I had to add the calculation step and the function epilog code.
Also, there was a bug where after main prints the number, there was no syscall 10 (exit) so the code would just fall through and recurse infinitely.
I reworked the C code slightly so it would be more compatible with the MIPS code.
Just for fun, and ease of testing, I changed main to loop and reprompt until it gets a negative number.
I've cleaned up and tested the code, added annotations [please pardon the gratuitous style cleanup]:
.data
# NOTE: these should appear first to maintain alignment to a 4 byte boundary
# (or the .align 4 will do it) otherwise, the lw/sw ops can fail on an
# alignment exception
.align 4
input: .word 0
answer: .word 0
promptMessage: .asciiz "Enter a number that is greater than or equal to 0 (-1 to stop): "
resultMessage: .asciiz "\nThe answer is: "
nl: .asciiz "\n"
.text .globl
main:
# prompt user
li $v0,4
la $a0,promptMessage
syscall
# Read the number from the user
li $v0,5
syscall
sw $v0,input
# negative value means stop
# NOTE: added this
bltz $v0,main_exit
# Call the function
lw $a0,input
jal recur
sw $v0,answer
# Display result message
li $v0,4
la $a0,resultMessage
syscall
# display number
li $v0,1
lw $a0,answer
syscall
# output newline
li $v0,4
la $a0,nl
syscall
# NOTE: this was added to allow multiple tries, but without it, there was
# the bug below
j main
# BUG: syscall to exit here was _missing_ so got fallthrough into "recur"
# causing the stack to overflow
main_exit:
li $v0,10
syscall
.globl recur
# recur -- recursion
#
# arguments:
# a0 -- the "n" value
#
# pseudo code:
# * int
# * recur(int n)
# * {
# * int r;
# *
# * if (n == 1 || n == 2) {
# * return 2;
# * }
# *
# * r = recur(n - 2);
# *
# * return (n - 4) + (n * r);
# * }
recur:
addi $sp,$sp,-8
sw $a0,0($sp)
sw $ra,4($sp)
# Base Case if(n == 0 || n == 1) return 2;
li $v0,2
beq $a0,$zero,recur_done
beq $a0,1,recur_done
# RECURSIVE STEP
addi $a0,$a0,-2 # n -= 2
jal recur
lw $a0,0($sp) # we need "n" back (not (n - 2))
# NOTE: this calculation was missing
mul $v0,$v0,$a0 # r *= n (i.e. (n * r))
addi $a0,$a0,-4 # n -= 4 (i.e. (n - 4))
add $v0,$v0,$a0 # sum them
# NOTE: this is the standard reversal for this function's stack prolog
recur_done:
lw $a0,0($sp)
lw $ra,4($sp)
addi $sp,$sp,8
jr $ra
这篇关于MIPS帮助：递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
