NASM大会递归斐波那契

Voldemort 发表于 Dev

伏地魔

在32位Ubuntu上学习NASM汇编。

我一直在学习递归函数。我刚刚做了阶乘，在您的帮助下：了解NASM组装中的递归阶乘函数

看着代码，我想也许我也可以使用几乎相同的代码快速实现斐波那契。这是代码，假设参数始终大于0：

SECTION .text
global main
main:
; -----------------------------------------------------------
; Main
; -----------------------------------------------------------
push    6
call    fibonacci
mov     [ECX],EAX
add     byte [ECX],'0'
mov     EDX,1
call    print

; -----------------------------------------------------------
; Exit
; -----------------------------------------------------------
mov EAX,1
int 0x80

; -----------------------------------------------------------
; Fibonacci recursivo: f(n) = f(n - 1) + f(n - 2)
; -----------------------------------------------------------
fibonacci:

push    EBP         ; Retrieve parameter and put it
push    EBX         ; Save previous parameter
mov     EBP,ESP     ; into EBX register
add     EBP,12      ;
mov     EBX,[EBP]   ; EBX = Param

cmp     EBX,1       ; Check for base case
jle     base        ; It is base if (n <= 1)

dec     EBX     ; Decrement EBX to put it in the stack
push    EBX     ; Put (EBX - 1) in stack
inc     EBX     ; Restore EBX
call    fibonacci   ; Calculate fibonacci for (EBX - 1)
mov ESI,EAX     ; EAX = (EAX + EBX)
pop EBX         ; Retrieve EBX from the stack

sub EBX,2       ; Decrement EBX to put it in the stack
push    EBX     ; Put (EBX - 2) in stack
add EBX,2       ; Restore EBX
call    fibonacci   ; Calculate fibonacci for (EBX - 2)
mov EDX,EAX     ; EAX = (EAX + EBX)
pop EBX         ; Retrieve EBX from the stack

add ESI,EDX
mov EAX,ESI

jmp end
base:               ; Base case
mov EAX,1           ; The result would be 1

end:

pop     EBX         ; Restore previous parameter
pop     EBP         ; Release EBP
ret

这有点粗糙。我计算斐波那契(parameter - 1)，然后再次计算，然后(parameter - 2)将它们加起来并放入EAX。

它不起作用：

2 => 2
3 => 3
4 => 4
5 => 4

幸运的是，我修复了细分错误，但是这样做可能会破坏其他功能。现在，我看不出问题所在。您能告诉我为什么我得到错误的值吗？

一个特殊的观察是，由于某种原因，这样做确实mov ECX,EAX给了我一个分割错误错误。这就是我ESI改用的原因。我不确定为什么，但是我想这是相关的。

麦可

每当处理递归时，都必须非常小心递归链中的下一层将对当前层的状态（例如寄存器值）进行处理。我建议重写函数，如下所示：

fibonacci:
push    EBP         ; Retrieve parameter and put it
push    EBX         ; Save previous parameter
mov     EBP,ESP     ; into EBX register
add     EBP,12      ;
mov     EBX,[EBP]   ; EBX = Param

cmp     EBX,1       ; Check for base case
jle     base        ; It is base if (n <= 1)

lea ecx,[ebx-1]
push ecx            ; push N-1
call    fibonacci   ; Calculate fibonacci for (EBX - 1)
pop ecx             ; remove N-1 off the stack

push eax            ; save the result of fibonacci(N-1)
lea ecx,[ebx-2]
push ecx            ; push N-2
call    fibonacci   ; Calculate fibonacci for (EBX - 2)
pop ecx             ; remove N-2 off the stack
pop ecx             ; ecx = fibonacci(N-1)
add eax,ecx         ; eax = fibonacci(N-2) + fibonacci(N-1)

jmp end
base:               ; Base case
mov EAX,1           ; The result would be 1

end:
pop     EBX         ; Restore previous parameter
pop     EBP         ; Release EBP
ret