因为递归需要的时间很长且重复调用，因此要对其进行优化
如何对以下代码进行优化
优化后仍然是递归算法
a0: parameter, initially n
s0: placeholder for parameter n
s1: fib(n-1)
s2: fib(n-2)
fib部分
fib:
##Part 1. Prologue as a callee
addi sp, sp, -16 #create its stack frame
sw ra, 12(sp) #save the return address to caller
sw s0, 8(sp) #callee saved registers
sw s1, 4(sp)
sw s2, 0(sp)
##Part 2. Main body
mv s0, a2 #addi s0, a2, 0 (parameter n saved in s0)
li t0, 2 #addi t0, x0, 2 (t0 = 2)
blt s0, t0, fib_base #if n < 2, do the base case
addi a2, s0, -1 #compute fib(n-1)
jal fib #jal ra, fib
mv s1, a0 #s1 = fib(n-1)
addi a2, s0, -2 #compute fib(n-2)
jal fib #jal ra, fib
mv s2, a0 #s2 = fib(n-2)
add a0, s1, s2 #a0 = fib(n-1) + fib(n-2)
b fib_ret #beq x0, x0, fib_ret
fib_base:
li a0, 1
##Part 3. Epilogue as a callee
fib_ret:
lw ra, 12(sp) #restore the return address
lw s0, 8(sp) #restore $s0
lw s1, 4(sp) #restore $s1
lw s2, 0(sp) #restore $s2
addi sp, sp, 16 #restore the stack pointer
jr ra #jalr zero, ra, 0
main部分：
main:
li a7, 5 #load syscall read_int into a7
ecall #make the syscall
mv a2, a0 #move the number read into a2
jal fib
li a7, 1 #load syscall print_int into $a7
ecall #make the syscall
li a7, 10 #progam exit system call
ecall
.include "fib.s"
|
楼主
标题置顶
标题高亮
