NASM大会递归斐波那契 [英] NASM Assembly recursive fibonacci
问题描述
在32位Ubuntu上学习NASM组装.
Learning NASM Assembly on 32-bit Ubuntu.
我一直在学习递归函数.我只是做了阶乘，在您的帮助下:了解NASM Assembly中的递归阶乘函数
I've been learning about recursive functions. I just did factorial, with your help here: Understanding recursive factorial function in NASM Assembly
看着代码，我想也许我也可以使用几乎相同的代码快速实现斐波那契.这是代码，假设参数始终大于0:
Watching the code, I thought that maybe I could quickly implement fibonacci as well, using almost the same code. Here is the code, assuming that the parameter is always greater than 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.
It is a bit crude. I calculate fibonacci for (parameter - 1), then I do it again for (parameter - 2), and just add them up and put them into EAX.
它不起作用:
2 => 2
3 => 3
4 => 4
5 => 4
幸运的是，我修复了分段错误，但是这样做可能会破坏其他功能.现在，我看不出问题所在.你能告诉我为什么我得到错误的值吗?
Fortunately I fixed the segmentation fault errors, but I probably broke something else doing that. Now I don't see what's the problem. Can you tell me why am I getting the wrong values?
一个特殊的观察结果是，由于某种原因，执行mov ECX,EAX给了我一个分段错误错误.这就是为什么我改用ESI的原因.我不确定为什么，但是我想这是相关的.
One particular observation is that, for some reason, doing mov ECX,EAX gave me a segmentation fault error. That's why I used ESI instead. I'm not sure why, but I guess that it is related.
推荐答案
无论何时处理递归，您都必须非常小心递归链中的下一层对当前层的状态(例如寄存器值).我建议如下重写该函数:
Whenever you're dealing with recursion, you have to be very careful about what the next layer in the recursive chain will do to the state of the current layer (e.g. register values). I'd suggest rewriting the function as follows:
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
这篇关于NASM大会递归斐波那契的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
