递归斐波那契集合

Question

我用汇编语言编写了一段代码，用于递归计算数字的斐波那契数列。该代码适用于 RISC V 处理器。对于数字 1 和 2，代码可以正确工作，但以上所有内容均未正确计算，并且寄存器写入不正确。 这是我的代码：

.text
.globl _start
.globl fib       # Export function 'fib'

# Entry point
_start:
    addi a0, x0, 4       # Load 4 into a0
    jal ra, fib          # Jump to fib

fib:
    # Check base cases
    addi t0, x0, 1              # Load 1 into t0
    beq a0, t0, base_case       # If n == 1, jump to base_case
    addi t0, x0, 2              # Load 2 into t0
    beq a0, t0, base_case       # If n == 2, jump to base_case

    # Recursive call for F(n-1)
    addi sp, sp, -4             # Allocate stack space for return address
    sw ra, 0(sp)                # Save return address on the stack
    addi sp, sp, -4             # Allocate stack space for intermediate results
    sw a0, 0(sp)                # Save current value of a0 (n)
    addi a0, a0, -1             # a0 = a0 - 1 (n-1)
    jal ra, fib                 # Call fib(n-1)
    lw t1, 0(sp)                # Load result of F(n-1) into t1
    addi sp, sp, 4              # Restore stack pointer
    lw ra, 0(sp)                # Load return address from the stack
    addi sp, sp, 4              # Restore stack pointer

    # Recursive call for F(n-2)
    addi sp, sp, -4             # Allocate stack space for return address
    sw ra, 0(sp)                # Save return address on the stack
    addi sp, sp, -4             # Allocate stack space for intermediate results
    sw t1, 0(sp)                # Save F(n-1) on the stack
    addi a0, a0, -1             # a0 = a0 - 1 (n-2)
    jal ra, fib                 # Call fib(n-2)
    lw t1, 0(sp)                # Load F(n-1) from the stack into t1
    addi sp, sp, 4              # Restore stack pointer
    lw ra, 0(sp)                # Load return address from the stack
    addi sp, sp, 4              # Restore stack pointer

    # Add results
    add a0, t1, a0              # a0 = t1 + a0 (F(n-1) + F(n-2))
    jalr x0, ra, 0              # Return to the calling function

base_case:
    addi a0, x0, 1              # Base case: result = 1
    jalr x0, ra, 0              # Return to the calling function

该代码旨在递归计算 F(n)，遵循公式 F(n) = F(n-1) + F(n-2) 。基本情况 F(1) = 1 和 F(2) = 1 终止递归，而结果存储在 a0 寄存器中。

堆栈用于存储返回地址（ra）和中间值（a0，t1，t2）。最初，堆栈管理不一致，导致结果不正确或数据损坏。

相同的寄存器 a0 用于输入值和结果，这导致了冲突和不正确的计算。

每个 jal（跳转和链接）指令都会覆盖 ra 的值。如果 ra 没有正确保存，程序就会丢失返回地址。

未一致检查基本情况 F(1) = 1 和 F(2) = 1，导致无限递归。

Answer 1

从根本上来说，你有两个调用约定错误。

虽然您的函数在

a0

中正确返回返回值（也称为答案），但您的函数在递归调用后并不期望它们出现！

例如这一行

lw t1, 0(sp)                # Load result of F(n-1) into t1

的实现和注释都不恰当，因为 F(n-1) 的结果已经在寄存器

a0

中，而不是在

0(sp)

的内存中。

0(sp)

中的内容是您在通话前存储的内容，即

n

。

第二个问题是您没有获得第二次递归调用的

n-2

。  虽然

n-1

被正确计算并传递给

F(n-1)

以进行第一个递归调用，但当它到达第二个递归调用时，寄存器

a0

现在保存来自第一个 F(n-1) 调用的返回值（不是原始的）

n

in

a0

），所以你正在做

F(F(n-1))

而不是

F(n-1)

，然后

F(n-2)

。