# 斐波那契数列

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181...

## 36.1　例一

``````#include <stdio.h>
void fib (int a, int b, int limit)
{
printf ("%d\n", a+b);
if (a+b > limit)
return;
fib (b, a+b, limit);
};

int main()
{
printf ("0\n1\n1\n");
fib (1, 1, 20);
};
``````

Listing 36.1: MSVC 2010 x86

``````_a\$ = 8         ; size = 4
_b\$ = 12        ; size = 4
_limit\$ = 16    ; size = 4
_fib    PROC
push    ebp
mov     ebp, esp
mov     eax, DWORD PTR _a\$[ebp]
add     eax, DWORD PTR _b\$[ebp]
push    eax
push    OFFSET \$SG2643
call    DWORD PTR __imp__printf
mov     ecx, DWORD PTR _a\$[ebp]
add     ecx, DWORD PTR _b\$[ebp]
cmp     ecx, DWORD PTR _limit\$[ebp]
jle     SHORT \$LN1@fib
jmp     SHORT \$LN2@fib
\$LN1@fib:
mov     edx, DWORD PTR _limit\$[ebp]
push    edx
mov     eax, DWORD PTR _a\$[ebp]
add     eax, DWORD PTR _b\$[ebp]
push    eax
mov     ecx, DWORD PTR _b\$[ebp]
push    ecx
call    _fib
\$LN2@fib:
pop     ebp
ret     0
_fib    ENDP

_main   PROC
push    ebp
mov     ebp, esp
push    OFFSET \$SG2647
call    DWORD PTR __imp__printf
push    20
push    1
push    1
call    _fib
xor     eax, eax
pop     ebp
ret     0
_main   ENDP
``````

``````0035F940  00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F944  00000008 1st argument: a
0035F948  0000000D 2nd argument: b
0035F94C  00000014 3rd argument: limit
0035F950 /0035F964 saved EBP register
0035F954 |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F958 |00000005 1st argument: a
0035F95C |00000008 2nd argument: b
0035F960 |00000014 3rd argument: limit
0035F964 ]0035F978 saved EBP register
0035F968 |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F96C |00000003 1st argument: a
0035F970 |00000005 2nd argument: b
0035F974 |00000014 3rd argument: limit
0035F978 ]0035F98C saved EBP register
0035F97C |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F980 |00000002 1st argument: a
0035F984 |00000003 2nd argument: b
0035F988 |00000014 3rd argument: limit
0035F98C ]0035F9A0 saved EBP register
0035F990 |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F994 |00000001 1st argument: a
0035F998 |00000002 2nd argument: b
0035F99C |00000014 3rd argument: limit
0035F9A0 ]0035F9B4 saved EBP register
0035F9A4 |00FD105C RETURN to fib.00FD105C from fib.00FD1000
0035F9A8 |00000001 1st argument: a           \
0035F9AC |00000001 2nd argument: b           | prepared in main() for f1()
0035F9B0 |00000014 3rd argument: limit       /
0035F9B4 ]0035F9F8 saved EBP register
0035F9B8 |00FD11D0 RETURN to fib.00FD11D0 from fib.00FD1040
0035F9BC |00000001 main() 1st argument: argc \
0035F9C0 |006812C8 main() 2nd argument: argv | prepared in CRT for main()
0035F9C4 |00682940 main() 3rd argument: envp /
``````

## 36.2 例二

``````#include <stdio.h>
void fib (int a, int b, int limit)
{
int next=a+b;
printf ("%d\n", next);
if (next > limit)
return;
fib (b, next, limit);
};

int main()
{
printf ("0\n1\n1\n");
fib (1, 1, 20);
};
``````

``````_next\$ = -4     ; size = 4
_a\$ = 8         ; size = 4
_b\$ = 12        ; size = 4
_limit\$ = 16    ; size = 4
_fib    PROC
push    ebp
mov     ebp, esp
push    ecx
mov     eax, DWORD PTR _a\$[ebp]
add     eax, DWORD PTR _b\$[ebp]
mov     DWORD PTR _next\$[ebp], eax
mov     ecx, DWORD PTR _next\$[ebp]
push    ecx
push    OFFSET \$SG2751 ; '%d'
call    DWORD PTR __imp__printf
mov     edx, DWORD PTR _next\$[ebp]
cmp     edx, DWORD PTR _limit\$[ebp]
jle     SHORT \$LN1@fib
jmp     SHORT \$LN2@fib
\$LN1@fib:
mov     eax, DWORD PTR _limit\$[ebp]
push    eax
mov     ecx, DWORD PTR _next\$[ebp]
push    ecx
mov     edx, DWORD PTR _b\$[ebp]
push    edx
call    _fib
\$LN2@fib:
mov     esp, ebp
pop     ebp
ret     0
_fib    ENDP

_main   PROC
push    ebp
mov     ebp, esp
push    OFFSET \$SG2753 ; "0\n1\n1\n"
call    DWORD PTR __imp__printf
push    20
push    1
push    1
call    _fib
xor     eax, eax
pop     ebp
ret     0
_main    ENDP
``````

``````0029FC14  00E0103A RETURN to fib2.00E0103A from fib2.00E01000
0029FC18  00000008 1st argument: a
0029FC1C  0000000D 2nd argument: b
0029FC20  00000014 3rd argument: limit
0029FC24  0000000D "next" variable
0029FC28 /0029FC40 saved EBP register
0029FC2C |00E0103A RETURN to fib2.00E0103A from fib2.00E01000
0029FC30 |00000005 1st argument: a
0029FC34 |00000008 2nd argument: b
0029FC38 |00000014 3rd argument: limit
0029FC3C |00000008 "next" variable
0029FC40 ]0029FC58 saved EBP register
0029FC44 |00E0103A RETURN to fib2.00E0103A from fib2.00E01000
0029FC48 |00000003 1st argument: a
0029FC4C |00000005 2nd argument: b
0029FC50 |00000014 3rd argument: limit
0029FC54 |00000005 "next" variable
0029FC58 ]0029FC70 saved EBP register
0029FC5C |00E0103A RETURN to fib2.00E0103A from fib2.00E01000
0029FC60 |00000002 1st argument: a
0029FC64 |00000003 2nd argument: b
0029FC68 |00000014 3rd argument: limit
0029FC6C |00000003 "next" variable
0029FC70 ]0029FC88 saved EBP register
0029FC74 |00E0103A RETURN to fib2.00E0103A from fib2.00E01000
0029FC78 |00000001 1st argument: a           \
0029FC7C |00000002 2nd argument: b           | prepared in f1() for next f1()
0029FC80 |00000014 3rd argument: limit       /
0029FC84 |00000002 "next" variable
0029FC88 ]0029FC9C saved EBP register
0029FC8C |00E0106C RETURN to fib2.00E0106C from fib2.00E01000
0029FC90 |00000001 1st argument: a           \
0029FC94 |00000001 2nd argument: b           | prepared in main() for f1()
0029FC98 |00000014 3rd argument: limit       /
0029FC9C ]0029FCE0 saved EBP register
0029FCA0 |00E011E0 RETURN to fib2.00E011E0 from fib2.00E01050
0029FCA4 |00000001 main() 1st argument: argc \
0029FCA8 |000812C8 main() 2nd argument: argv | prepared in CRT for main()
0029FCAC |00082940 main() 3rd argument: envp /
``````

## 36.3 总结

By the way，这是一些函数式PL（Programming language，编程语言，LISP, Python, Lua等）编译器（其中大量使用递归）使用tail call的原因。