用汇编语言剖析递归算法的内在机理

火善栋 杨旭东

（1.重庆三峡学院，重庆万州 404000）

（2.重庆安全技术职业学院，重庆万州 404000）

0 引 言

递归算法是计算机领域中一个很重要的算法，通过递归算法可以使很复杂的问题变得很容易解决，例如著名的汉诺塔问题，假若不采用递归算法的话可能无法解决，还有数据结构中树和图的遍历，通过采用递归算法从而使问题变得非常容易，当然递归算法在很多地方也有着很广泛的应用.

递归算法虽然编写起来比较容易，但在对递归算法的理解上，很多人却感到很抽象，在学习过程中往往对这类问题的执行过程不了解，对递归问题的认识不清楚，所以难以写出正确的递归程序，另外，在对递归算法的执行效率以及空间复杂度上很多人更是感到难以理解.这其中一个很重要的原因就是对递归算法的内在机理没有搞清楚，对递归算法中函数如何反复调用以及参数如何进行传递没有理解透彻.

由于高级语言把程序运行的内部细节都透明化了，所以想通过高级语言理解递归算法的内在运行机理是不可能的，但汇编语言是一门低级语言，其实质也是机器语言一对一的符号化，是指令级的语言，虽然通过汇编语言编写程序代码费时费力，但通过汇编语言可以看出程序运行的每一个细节.因此，这对理解递归算法无疑是一个很好的工具.

1 实例分析

本文通过一个很简单的递归算法的例子“斐波那契（Fibonacci）数列”来具体剖析递归算法的内在运行机理，从而加深对递归算法的理解，进而帮助读者更好地用好递归算法.

【问题】编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）.

斐波那契数列为：0、1、1、2、3、……，即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2) （当n>1时）

写成递归函数通常是：

为了使这个简单的递归算法更具有代表性以及分析在递归算法内部参数是如何传递的，本文把上述代码改写成“表1”左面所示的形式（C语言代码）.

“表 1”是“斐波那契（Fibonacci）数列”递归算法的C语言实现代码以及对应的反汇编代码，“图 1”是通过分析反汇编代码得出的该算法的堆栈变化示意图.

从下面这段反汇编代码中可以看出，C程序中的递归函数对应的反汇编代码是一个远调用子过程，其整个调用过程的基本情况和执行过程如下：

1.1 进行函数调用时首先将函数的参数（形参）压入堆栈（在C语言中压入的顺序是从右到左，由于本实例只有一个参数，所以没有反应出来），本例是通过SI寄存器来实现这一过程的.

1.2 将函数的返回地址即该函数下一条将要执行指令的地址压入堆栈（由于本实例是远调用，所以将CS和IP的值压入了堆栈）同时修改CS和IP寄存器的值，跳转到要执行指令的起始位置，从而实现了函数的调用.

1.3 将BP的值压入堆栈保护BP寄存器的值为以后恢复栈顶指针（SP）做准备，然后将SP的值赋给BP，再通过BP访问堆栈中传入参数和函数体内部定义的局部变量.

1.4 将函数体内部定义的局部变量压入堆栈，本实例定义了三个局部变量，但只压入了两个，这个过程是通过SUB SP 4来实现的，有一个作为返回值没有压入.

1.5 为了保证函数调用的透明性，将其调用过程中要用到寄存器的值（SI，DI）压入堆栈.

1.6 以上过程为函数体代码的执行作好了准备，紧接的过程就是通过BP来实现函数参数的传递，并将中间结果保存在局部变量中，这一过程全部是通过对堆栈的操作来实现的.

表1 斐波那契数列递归调用C语言与汇编代码对比表

图1 堆栈变化示意图

1.7 每一次函数调用结束之后，恢复中间寄存器（本实例是SI，DI）以及SP，BP的值，本实例通过POP DI，POP SI，MOV SP，BP以POP BP来实现的.返回结果最后保存在AX寄存中，在本实例中函数体内部的递归调用也是通过AX来实现参数传递的.另外由于主函数体的调用是一个FAR调用，而函数体内部调用是一个near调用，为了实现递归调用过程的统一性，本实例通过PUSH CS和这一条指令来实现了递归调用的一致性工作，从而保证了代码执行的高效性.

1.8 函数调用结束之后，SP和BP基本恢复为调用前的初始状态，但函数在执行retf指令之后，堆栈还没有完全清空，里面还保留着传入参数的值，所以本实例通过POP CX这一指令来实现了清栈工作（这一情况会随传入参数个数的不同而有不同）.

总之，函数在执行调用之后，堆栈完全恢复为调用前的最初始状态，只是结果保存在AX寄存器中，进而实现了函数调用的透明性.

笔者认为，理解递归调用的一个重要难点就是要搞清楚在递归调用内部是如何进行参数传递的，以及返回值是如何保存的.通过对以上反汇编代码的分析可以看出，AX寄存器起到了一个很重要的作用，以AX寄存器作为桥梁，不断地和堆栈交换数据，不断地将中间结果保存在AX寄存器中，从而很轻松地实现了参数的传递和结果的保存.

通过以上分析，可以得出“斐波那契（Fibonacci）数列”递归算法（n=5）的具体执行过程，如图 2所示：

图2 递归调用示意图

从图二中可以看出，“斐波那契（Fibonacci）数列”递归算法的递归调用过程非常像一颗二叉树中的前序遍历，这是由于递归函数体fibo（n）中有两个函数体fibo（n-1）和fibo（n-2）所造成的，由此可以推出当递归函数体有三个甚至n个函数体的情况，当然当递归函数体只有一个函数体时，这是一种最简单的递归调用形式.

2 结 论

递归算法实质就是一个函数体不断调用自身的过程，在调用的过程中不断地将参数、返回地址以及局部变量压入堆栈，当返回时又将堆栈恢复到每一次调用前的状态.在整个调用过程中，始终以AX或EAX寄存器作为桥梁，不断地和堆栈交换数据，不断地将中间结果保存在AX或EAX寄存器中，从而顺利地实现了参数的传递和结果的返回.另外，递归函数在执行递归调用的过程，要不断地执行进栈和出栈操作，所以执行效率相对要低一些；同时，递归算法内存的消耗也主要是用在堆栈的花销上，但堆栈对内存的占用是一个不断变化的动态过程，因此，其最大占用内存是由递归调用的最深层次决定的.

就对递归算法的理解而言，我们可以将其视为一个树形结构，当递归函数体中有两个递归函数时，其执行过程类似于二叉树的前序遍历.推而广之，当递归函数体中有n个递归函数时，就相当于这颗树中有n个分枝，也就是形式上的“n叉树”.

[1]谭文等.天书夜读：从汇编语言到 Windows内核编程[M].北京：电子工业出版社，2008，10.

[2]火善栋.通过汇编语言理解函数调用的内在机理[J].计算机时代，2010（7）.

[3]吕凤翥.C++语言程序设计[M].北京：清华大学出版社，2003，7.

[4]卜艳萍.汇编语言程序设计教程：第二版[M].北京：清华大学出版社，2008，7.

[5]邵桂芳，李刚，张小川.多媒体技术在汇编语言程序设计课程中的应用[J].重庆工学院学报：自然科学版，2007（11）.

[6]杨隆平.SQL语言在VB中的优化应用[J].重庆三峡学院学报，2010（3）.