转载自微信公众账号：开点工作室（ID：kaidiancs）

阿里2015笔试中有这样一道题目：

在一台主流配置的PC上，调用f(35)所需要的时间大概是（）。

int f(int x){

int s = 0;

while(x++ >0)s+= f(x);

return max(s,1);

}

A．几毫秒B．几秒C．几分钟D．几小时

本题涉及到的知识点包括数据的表示和运算、时间复杂度。考查考生对带符号整数的表示、递归调用的执行过程、计算机系统性能、虚拟存储器、C语言语句等相关知识的理解和运用能力。

数学上的分析推导结果与计算机系统中的执行结果是有差异的。例如，在数学中一个数可以无限大，但在计算机中受表示位数的限制，数的值是有限的。用数学分析的方法，本题的递归是可以终止的，但受存储容量的限制，在计算机中递归调用时会有栈溢出的问题，导致程序不能正常执行结束。类似的问题还有很多，这是平时编程时需要注意的。

假设题目中的函数用C语言书写，要分析调用f(35)所需的时间，就得分析代码执行中循环执行次数和递归调用次数等，下面深入剖析f(35)执行过程中存在的问题。

（1）程序是否会终止？

调用f(35)时，入口参数x=35。从数学的角度理解while中的判断表达式“x++ >0”，会认为x在增量后永远大于0，这是一个永真式，从而做出错误结论：程序死循环。在计算机中数值是有范围的，int型数据用补码表示，占4个字节，能表示的最大正数是2-1 = 7FFFFFFFH。231的机器数是8000 0000H，其值为int型能表示的最小负数-2147483648，因此当x= 8000 0000H时，x> 0的值为假，程序退出while循环，因此，若不考虑栈溢出，则程序能执行结束。

（2）使递归终止的最大x值是多少？

while(x++ >0)语句在Microsoft VC中的机器代码如下，该语句的执行过程是：先把x的值分别保存到EDX和EAX寄存器；然后对EAX寄存器内容加1，以实现x=x+1操作；最后再用EDX的内容（x的旧值）进行x>0的条件判断。

mov       edx, dword ptr [ebp+8]

mov        eax,dword ptr [ebp+8]

add        eax, 1

mov       dword ptr [ebp+8], eax

test        edx, edx

jle         f+77h (00401097)

因此，当调用f(231-1)时，x= 231-1=7FFF FFFFH，先执行x=7FFF FFFFH+1 = 8000 0000H=231，然后，用旧的x=7FFF FFFFH与0比较，比较结果为真，故执行while循环体，在循环体中调用f(231)。

调用f(231)时，x为231= 8000 0000H，其真值为负数，因此，与0比较的结果为假，故跳出while循环体，程序结束。

综上所述，使递归终止的最大x值是231，即执行f(231)时结束递归调用。

（3）函数f(x)的递归调用情况如何？

f(x)是一个递归调用过程，并且递归调用在循环体内，因此调用关系较复杂。图1显示了f(231-4)执行中的递归调用情况。

图1f(231-4)执行中的递归调用情况

在f(x)执行过程中，把执行f(x)过程体的总次数记为f(x)执行次数，把一次递归调用的最大次数记为f(x)递归深度。表1给出了x为不同值时，执行f(x)的次数和递归深度。这两个参数显示了f(x)函数的执行过程。

（4）递归调用过程的执行情况

系统会给每一个用户进程分配存放代码和数据的用户空间，用户空间中的栈区用来存放程序运行时过程调用的参数、返回地址、过程局部变量等。随着程序的执行，栈区不断动态地从高地址向低地址增长或向反方向减退。

用户栈由若干个栈帧组成，每个过程对应一个栈帧，帧指针寄存器EBP指定一个栈帧的起始地址，栈指针寄存器ESP指向栈顶，当前栈帧的范围在EBP和ESP指向的区域之间。过程执行时，由于不断有数据入栈，所以栈指针ESP会动态移动，而帧指针EBP固定不变。在一个过程内对栈中信息的访问大多通过帧指针EBP进行。

IA-32规定，寄存器EAX、ECX和EDX是调用者保存寄存器，EBX、ESI、EDI寄存器是被调用者保存寄存器。若过程P调用过程Q时，P在需要时先在自己的栈区保存EAX、ECX和EDX、入口参数和返回地址，接着跳转到Q执行。Q在自己的栈帧中先保存P的EBP值，并设置EBP指向当前Q栈帧的栈低，根据需要保存EBX、ESI、EDI，再在栈中给Q的局部变量分配空间。

在递归调用执行中，每个递归调用过程都有一个栈帧。栈帧中可能包含如图2所示的信息。

图3显示了在windows系统中f(x)函数调用时的部分机器指令。可以看出f(x)的栈帧至少有84B。系统分配给一个进程的用户栈只有有限的空间，因此，递归调用的次数是有限的。f(35)的递归深度是2147483614，即至少需要2147483614×84字节，即大于170GB的栈帧空间。在32位系统中，最大虚拟地址空间仅有4GB，用户栈只是其中的一部分，所以f(35)在执行过程中会出现栈溢出的现象。

图3 f(x)函数调用时的部分机器指令

（5）f(35)在32位系统中的实际执行情况

假设在Intel x86+windows+VC+C语言环境中执行f(35)。VC中默认分配栈的大小是1MB，虽然用户可以调整栈大小，但栈的容量是有限的。按2MB的栈空间、栈大小按80字节计算：2MB÷80B≈26214，因此f(x)递归调用的次数不会超过26214-1=26213次。从图4.9中可以看出，栈溢出时，f(x)函数体最多执行26213次。栈溢出时每个f(x)函数体只在while语句中执行，假设每个f(x)函数体执行100条指令，即使指令平均CPI为3，时钟频率为2.4GHz，f(35)的执行时间也只有26213×100×3÷2.4GHz ≈3.2 ms左右时间。

对f(35)的执行做了测试，在栈大小是1MB时，递归调用11244次后栈溢出；在栈设置为2MB时，递归调用22642次后栈溢出，显然运行时间只有几毫秒。在Microsoft VisualStudio 2012环境中运行，出现如图4所示结果，表明出现了栈溢出（Stack overflow）。

综上所述，答案为A。

由此可以看出，虽然该题只是一道简单的选择题，其中蕴藏着的背景知识却非常丰富，该题完全可以变换成一道面试中的综合题目，考查应聘者是否能够熟悉相关的背景知识，并且能够根据这些基础知识进行合理有效的分析。