NASM大會遞歸斐波納契

Question

在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代替。我不知道爲什麼，但我想這是相關的。

Answer 1

無論何時處理遞歸，您都必須非常小心遞歸鏈中的下一層將對當前圖層的狀態（例如寄存器值）做什麼。我建議重寫功能如下：

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