递归斐波那契汇编 [英] Recursive fibonacci Assembly
问题描述
今天,我在汇编中编写了递归斐波那契,但它不起作用.我使用NASM将其编译为目标文件,然后使用gcc将其制成精灵.
当我输入1或2时,该功能可以正常运行,但是当我输入3、4、5、6或更多时,该功能不起作用.我认为函数调用自身存在问题.
Today I wrote a recursive fibonacci in assembly and it doesn't work. I compiled it to object file with NASM and than made it elf with gcc.
When I enter 1 or 2 the function works perfectly, but when I enter 3, 4, 5, 6, or more the function doesn't work.
I think there is problem where the function calls itself.
此代码:
SECTION .data ;init data
str: db "This equal: %d",10,0
SECTION .text ;asm code
extern printf
global main
main:
push ebp
mov ebp,esp
;--------------------
push 03 ; the index
call _fibonacci
add esp,4
push DWORD eax
push str
call printf
;---------------------
mov esp,ebp
pop ebp
ret
这是功能:
_fibonacci:
push ebp
mov ebp,esp
mov ebx, [ebp+8] ;; param n
cmp ebx,0
jne CHECK2
mov eax,0
jmp _endFIbofunc
CHECK2:
cmp ebx,0x1
jne ELSE3
mov eax,1
jmp _endFIbofunc
ELSE3:
mov ebx,[ebp+8]
dec ebx ;; n-1
;; FIRST call
push ebx
call _fibonacci
add esp,4
mov edx,eax
;; SEC CALL
dec ebx
push ebx
call _fibonacci
add esp,4
add eax,edx
mov eax,[ebp-4]
_endFIbofunc:
mov esp,ebp
pop ebp
ret
在Ubuntu 16.04上运行它后,它发送错误:
After I ran it on Ubuntu 16.04 it send error:
分段错误(核心已转储)
Segmentation fault (core dumped)
可能是什么问题?
推荐答案
除了提供的其他答案之外,还有另一种解决方法:
In addition to the other answers provided, here's an alternate solution:
_fibonacci:
mov eax,[esp+4] ;eax = n
cmp eax,2 ;br if n < 2
jb _endFIbofunc
dec eax ;push n-1
push eax
call _fibonacci ;returns eax = fib(n-1)
xchg eax,[esp] ;eax = n-1, [esp] = fib(n-1)
dec eax ;push n-2
push eax
call _fibonacci ;returns eax = fib(n-2)
add eax,[esp+4] ;eax = fib(n-1)+fib(n-2)
add esp,8
_endFIbofunc:
ret
琐事-fib(47)是最大的<2 ^ 32.递归调用的数量= 2 * fib(n + 1)-1.
Trivia - fib(47) is the largest < 2^32. The number of recursive calls = 2*fib(n+1)-1.
n fib(n) # calls
0 0 1
1 1 1
2 1 3
3 2 5
4 3 9
5 5 15
6 8 25
7 13 41
8 21 67
9 34 109
10 55 177
11 89 287
12 144 465
13 233 753
14 377 1219
15 610 1973
16 987 3193
17 1597 5167
18 2584 8361
19 4181 13529
20 6765 21891
21 10946 35421
22 17711 57313
23 28657 92735
24 46368 150049
25 75025 242785
26 121393 392835
27 196418 635621
28 317811 1028457
29 514229 1664079
30 832040 2692537
31 1346269 4356617
32 2178309 7049155
33 3524578 11405773
34 5702887 18454929
35 9227465 29860703
36 14930352 48315633
37 24157817 78176337
38 39088169 126491971
39 63245986 204668309
40 102334155 331160281
41 165580141 535828591
42 267914296 866988873
43 433494437 1402817465
44 701408733 2269806339
45 1134903170 3672623805
46 1836311903 5942430145
47 2971215073 9615053951
48 4807526976 ...
这篇关于递归斐波那契汇编的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!