如何使用RISC-V对斐波那契递归算法进行优化

Question

因为递归需要的时间很长且重复调用，因此要对其进行优化
如何对以下代码进行优化
优化后仍然是递归算法

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"

Answer 1

提供一个优化思路，看你是否可以用指令写出
用一个中间缓存，示例代码如下：

int buf[52] = {0};  //中间buf存放中间结果，避免重复计算
int fib(n)
{
    int tmp=0;
    if(buf[n] != 0 ) return buf[n];
    if(n==1 || n==2) return 1;
    tmp = fib(n-1)+fib(n-2);
    buf[n] = tmp;
    return tmp;
}