- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试为函数 f(n) = 2f(n-1) + 3f(n-2) + 1
实现双递归.我能够找出奇异递归并实现 2f(n-1) + 1
它的一部分,但我无法弄清楚如何实现第二部分。这是我的奇异递归的工作代码:
.data
prompt1: .asciiz "Enter the value for the recursive function f(n) = 2f(n-1)+3f(n-2)+1: "
prompt2: .asciiz "Result: "
numberEntered: .word 0
answer: .word 0
.text
main:
#Ask for the value
li $v0 4
la $a0, prompt1
syscall
#enter value
li $v0, 5
syscall
sw $v0, numberEntered #stores the number
# call the function
lw $a0, numberEntered
jal function
sw $v0, answer
#Print out the result
li $v0 4
la $a0, prompt2
syscall
lw $a0, answer
li $v0, 1
syscall
li $v0, 10
syscall
.globl function
function:
subu $sp, $sp, 8
sw $ra, ($sp)
sw $s0, 4($sp)
#base case
li $v0, 1
beq $a0, $zero, done
#calling f(n-1)
move $s0, $a0
sub $a0, $a0, 1
jal function
#calculations occur here
mul $v0, $v0, 2
addi $v0, $v0, 1
done:
lw $ra, ($sp)
lw $s0, 4($sp)
addi $sp, $sp, 8
jr $ra #returns
最佳答案
相当不错的努力。
回答你的问题:你可以简单地在 function
建立一个堆栈框架最后进入并从中恢复。
我确实必须重新调整用途 $s0
稍微存储一个中间值并将其添加到堆栈帧中的存储值(即堆栈帧现在是 3 个字而不是 2 个)。
无论如何,这是更正后的代码。我试图对其进行一些注释(IMO,在 asm 中,没有“评论太多”这样的东西)[请原谅无偿的风格清理]:
.data
prompt1: .asciiz "Enter the value for the recursive function f(n) = 2f(n-1)+3f(n-2)+1: "
prompt2: .asciiz "Result: "
numberEntered: .word 0
answer: .word 0
.text
main:
# Ask for the value
li $v0,4
la $a0,prompt1
syscall
# enter value
li $v0,5
syscall
sw $v0,numberEntered # stores the number
# call the function
lw $a0,numberEntered
jal function
sw $v0,answer
# Print out the result
li $v0,4
la $a0,prompt2
syscall
lw $a0,answer
li $v0,1
syscall
li $v0,10
syscall
.globl function
# function -- calculation
# v0 -- return value
# a0 -- current n value
# s0 -- intermediate result
function:
subi $sp,$sp,12 # establish our stack frame
sw $ra,8($sp) # save return address
sw $a0,4($sp) # save n
sw $s0,0($sp) # save intermediate result
# base case
# NOTE: with the addition of n-2, the "beq" was insufficient
li $v0,1
ble $a0,$zero,done
# calling f(n-1)
sub $a0,$a0,1 # get n-1
jal function
# NOTE: these could be combined into a single instruction
mul $v0,$v0,2 # get 2f(n-1)
move $s0,$v0 # save it
# calling f(n-2)
sub $a0,$a0,1 # get n-2
jal function
mul $v0,$v0,3 # get 3f(n-2)
# get 2f(n-1) + 3f(n-2) + 1
add $v0,$s0,$v0
add $v0,$v0,1
done:
lw $ra,8($sp) # restore return address
lw $a0,4($sp) # restore n
lw $s0,0($sp) # restore intermediate result
addi $sp,$sp,12 # pop stack frame
jr $ra # returns
This solution is way simpler than I thought it would be.
int
whatever(int n)
{
int x;
// point A
x = other(1);
// do lots more stuff ...
{
// point B
int y = other(2);
// do lots more stuff ...
// point C
n *= (x + y);
}
// do lots more stuff ...
n += ...;
return n;
}
whatever
时建立一个堆栈帧。这将为
x
保留空间和
y
即使
y
只是在很晚之后才设置。大多数 C 程序员没有意识到这一点。
java
、
python
等)中,
y
的空间直到
point B
处的代码才保留被执行。而且,他们 [通常] 会在
y
时解除分配它进入“超出范围”[之后
point C
]。
y
] 节省堆栈空间。 (即)在作用域块中,编译器将增加堆栈帧大小以适应
y
并在
y
时再次收缩它不再需要。
y
]。
function
中所做的.即使我们不需要/使用
$s0
的堆栈空间 [at offset 0] 也是如此。直到函数的中间。
function
的调用约定不符合 ABI。如果它是自包含的(即不调用其他任何东西),这是完全没问题的。也就是说,在 asm 中,对于“叶”函数,我们可以定义任何我们想要的。
$a0
调用被被调用者修改/删除。我们从堆栈中保存/恢复了它,但是调用另一个函数可能会把事情搞砸。补救措施只是使用另一个寄存器来保存值[或保存/恢复到堆栈帧中的额外位置],因此如果
function
需要做更多的工作。最终调用别的东西。
关于recursion - 使用 MIPS 的双递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35593184/
虽然我在理解递归方面没有任何问题,但我似乎无法理解汉诺塔问题的递归解决方案。这是来自 Wikipedia 的代码: procedure Hanoi(n: integer; source, dest,
虽然我在理解递归方面没有任何问题,但我似乎无法理解汉诺塔问题的递归解决方案。这是来自 Wikipedia 的代码: procedure Hanoi(n: integer; source, dest,
The Third Commandment的 The Little Schemer状态: When building a list, describe the first typical elemen
编辑 有关映射递归的“正确”Groovy 式方法,请参阅下面的@tim 解决方案。由于 Map findRecursive 在 Groovy 中尚不存在,如果您发现自己在应用程序的各个部分都需要此功能
这是尝试求解 3*3 的线性方程并打印结果,但在注释行中遇到了问题: 我在程序外部定义了 LinearSolution 模块,我应该在程序内部定义它吗?有什么区别? 为什么说该语句是递归的,你知道,当
我正在学习 Clojure 并从复制 Python 程序的功能开始,该程序将通过遵循(非常简单的)隐马尔可夫模型来创建基因组序列。 一开始,我坚持使用我已知的串行编程方式并大量使用 def 关键字,从
我有一个记录: type node = { content : string; parent : node option;
我发现 Java 8 已经显着清理了将文件内容读取到字符串中的过程: String contents = new String(Files.readAllBytes(Paths.get(new URI
我目前正在用 Java 编写一个图形库,我想要一个工具来可视化一些图形。我发现了 Graph-viz,它恰好是一种很好的(尽管有缺陷)做到这一点的方法。 在我的模型中,图由节点和边组成。每个节点都有一
昨天我遇到了这个pipes Common Lisp 库。它在某种程度上看起来很像 clojure 的惰性序列抽象,因此我决定使用它来实现 Common Lisp 中递归惰性斐波那契序列定义的经典(且优
昨天我遇到了这个pipes Common Lisp 库。它在某种程度上看起来很像 clojure 的惰性序列抽象,因此我决定使用它来实现 Common Lisp 中递归惰性斐波那契序列定义的经典(且优
我在开发一个递归函数时遇到了问题,该函数将查看两个列表是否彼此相等,包括查看子列表。到目前为止,我有: (defun are-equal2 (X Y) (cond ((null X) nil)
在 Abelson/Sussman 的经典著作《计算机程序的结构和解释》中,在关于树递归和斐波那契数列的第 1.2.2 节中,他们展示了这张图片: 计算第 5 个斐波那契数时生成的树递归过程 然后他们
SICP中的Section 1.2.1 中的作者在下面给出了这样的代码示例,以显示如何使用迭代过程解决阶乘问题: (define (factorial n) (fact-iter 1 1 n))
我继承了 的遗产Fortran 77 我现在的代码 试试 前往 编译 Fortran 2003 标准。我对 Fortran (我知道 C 和 Python)一无所知,我正在学习它。 下面的代码片段会导
这个警告来自哪里: Warning: `recursive` is deprecated, please use `recurse` instead 我在这里看到过:https://r-pkgs.or
Section 2.2 of the Happy user manual建议您使用左递归而不是右递归,因为右递归是“低效的”。基本上他们是说,如果您尝试解析一长串项目,右递归将溢出解析堆栈,而左递归使
问题 我有一个递归 CTE 查询,但是在创建循环时它失败了。我已经修复了简单的循环(例如 1 -> 2 -> 1),但无法修复更复杂的循环(例如 1 -> 2 -> 3 -> 2)。 查询详情 测试表
看完麻省理工学院的动态规划讲座后,我想练习一下斐波那契数列。我首先编写了朴素的递归实现,然后添加了内存。这是内存版本: package main import ( "fmt" ) func f
按照以下步骤,Cloudformation 堆栈可以进入递归锁: 在不导入值的情况下设置 CF(并创建堆栈) 使用相同的 CF 模板创建 soms 输出值(并更新堆栈) 在同一 CF 模板(和更新堆栈
我是一名优秀的程序员,十分优秀!