在 32 位 Ubuntu 上学习 NASM 汇编。
我一直在学习递归函数。在你的帮助下,我刚刚做了阶乘:Understanding recursive factorial function in NASM Assembly
看着代码,我想也许我也可以使用几乎相同的代码快速实现斐波那契数列。下面是代码,假设参数总是大于 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
关于linux - NASM 汇编递归斐波那契数列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19220340/