第36章 斐波拉契数列

在计算机编程方面的教科书里,我们通常都能找到Fibonacci数列(斐波拉契数列)(以下简称为“Fibonacci”)的生成函数。其实这种数列编排的规则非常简单:从第三项开始,后续数字为前两项数字之和。头两项一般为0和1;也有头两项都是1的情况。因此,常见的Fibonacci数列大致如下:

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

36.1 例子1

Fibonacci的实现方法比较简单。举例来说,下面这个程序可以生成数值不超过21的数列各项:

#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);
};

指令清单36.1 MSVC 2010 x86

_TEXT    SEGMENT
_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 $SG2750 ; "%d"
        call    DWORD PTR __imp__printf
        add     esp, 8
        mov     ecx, DWORD PTR _limit$[ebp]
        push    ecx
        mov     edx, DWORD PTR _a$[ebp]
        add     edx, DWORD PTR _b$[ebp]
        push    edx
        mov     eax, DWORD PTR _b$[ebp]
        push    eax
        call    _fib
        add     esp, 12
        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
        add     esp, 4
        push    20
        push    1
        push    1
        call    _fib
        add     esp, 12
        xor     eax, eax
        pop     ebp
        ret     0
_main   ENDP

我们重点分析这个程序的栈结构。

我们在OllyDbg中加载本例生成的可执行程序,并跟踪到调用f()函数的那条指令,如图36.1所示。

3601{}

图36.1 OllyDbg最后一个函数f()

让我们来仔细分析栈里的内容。在下面的程序行中,笔者用打括弧的方法加了两个注释。一个是main()为f1()做准备,另外一个是CRT为main()做准备[1]

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  /

本例属于递归函数[2]。递归函数的栈一般都是这样的“三明治”结构。在上述程序中,limit(阈值)参数总是保持不变(十六进制的14,也就是十进制的20),而两个参数ab在每次调用函数的时候都是不同的值。此外栈也存储了RA和保存EBP(扩展堆栈指针)的值。OllyDbg能基于EBP的值判断栈的存储结构,因此它能够用括弧标注栈帧。换而言之,在每个括弧里的一组数值都形成了一个相对独立的栈结构,即栈帧(stack frame)。栈帧就是每次函数调用期间的数据实体。另一方面,即使从纯萃技术方面看每个被调用方函数确实可以访问栈帧之外的栈存储空间,但是正常情况下不应当访问栈帧之外的数据(当然除了获取函数参数的操作以外)。对于没有bug(缺陷)的函数来说,上述命题的确成立。每一个 EBP值都是前一个栈帧的地址。因此调试程序能够把数据栈识别为栈帧,并能识别出每次调用函数时传递的参数值。

结合上述指令可知,递归函数应当为下一轮的自身调用制备各项参数。

在程序的最后部分,main()有3个参数。其中argc(参数总数)为1。确实如此,笔者的确未带参数直接运行并调试本程序。

另外,调整本程序、引发栈溢出的过程并不复杂:我们只需要删除或者注释掉阈值limit判断语句,即可导致栈溢出(即错误编号为0xC00000FD的异常错误)。

36.2 例子2

上一节的函数有些冗余。接下来,我们增加一个新的局部变量next,并用它来代替所有程序中的a+b:

#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);
};

这是非优化MSVC的输出,因此next变量确实是在本地栈中分配存储空间。

指令清单36.2 MSVC 2010 x86

_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
        add     esp, 8
        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
        add     esp, 12
$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
        add     esp, 4
        push    20
        push    1
        push    1
        call    _fib
        add     esp, 12
        xor     eax, eax
        pop     ebp
        ret     0
_main   ENDP

我们再来调用OllyDbg,如图36.2所示。

3602{}

图36.2 OllyDbg: 最后调用f()

现在,每个栈帧里都有一个变量next。

我们来仔细看看堆栈。笔者依然给其中增加了注释。

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 总结

递归函数只是看起来很帅而已。从技术上讲,递归函数在栈方面的开销过大,因而性能不怎么理想。注重性能指标的应用程序,应当避免使用递归函数。

笔者曾经编写过一个遍历二叉树、搜索既定节点的应用程序。把它写成递归函数的时候,整个程序确实又清爽又有条理性。但是每次函数调用都得进行赋值、回调,这使得递归函数比其他类型的函数慢了数倍。

另外,部分PL[3]编译器会对递归调用采取“尾部调用”的优化方法,以减轻栈的各种开销。


[1] 在OllyDbg中,可以选择多项指令,再使用Ctrl+C组合键把它们复制到剪切板中。本例就是这样做的。

[2] 也就是自己调用自己。

[3] PL:Program Language(编程语言)。LISP、Python、Lua等编程语言的编译器能够进行尾部调用优化。详情请参阅https://en. wikipedia.org/wiki/Tail_call。