计算14的阶乘时迭代与递归实现运行时间近乎相等的原因探究

运行如下测试代码统计两种阶乘实现的运行时间时，1000次测试中有995-999次结果显示，计算14的阶乘时迭代实现与递归实现的运行时间差小于10微秒，几乎相等：

import time

def factorialIterative(n):
    result = 1
    for i in range(2, n+1):
        result = result * i
    return result

def factorialRecursive(n):
   if n == 1:
       return n
   else:
       return n*factorialRecursive(n-1)

def findRunTime(functionToCheck,parameter):
    startingTime = time.time()
    functionToCheck(parameter)
    endingTime = time.time()
    return endingTime-startingTime

count = 0

for i in range(1000):
    delta = findRunTime(factorialIterative,14) - findRunTime(factorialRecursive,14)
    if -0.00001 < delta < 0.00001:
        count=count+1

print(count)

初步观察到的规律如下：

• 两种实现的理论时间复杂度均为O(n)，但n≤14时递归实现速度甚至略快于迭代实现，和"递归性能差于迭代"的常规认知不符
• 当n>14后，迭代实现的性能才会稳定超过递归实现
• 最初推测该现象和调用栈大小、result变量内存占用有关，但该推论无法被验证成立。

根本原因 #

这个现象没有任何玄妙的内存匹配机制，本质是不同实现的固定开销、随n增长的可变开销在特定n值下恰好持平，叠加基准测试的精度误差导致的：

1. 计时方法天生带测量误差
   你用的time.time()在多数操作系统上的计时最小分辨率在1~10微秒级别，而n=14时两个函数的实际执行时间都不到1微秒，远低于计时工具能可靠测量的下限。你测到的运行时间里，99%以上是Python解释器调度、系统后台任务中断、函数调用准备的杂项开销，两个函数本身的执行差异被这些杂项噪声完全盖住，才会出现99%以上的测试结果差值落在10微秒阈值内的情况。
2. 两类实现的开销构成不一样
   两个函数的开销不是纯粹跟着n线性涨的，都有启动就要花的固定成本：
   • 迭代实现的固定成本来自range(2, n+1)对象的创建、循环变量的初始化，跟着n涨的可变成本是每次循环的变量取值、乘法运算、循环是否结束的判断、循环变量递增
   • 递归实现没有创建range对象的固定成本，跟着n涨的可变成本是每一层递归的栈帧分配、函数参数传递、返回值处理、乘法运算
     当n很小（≤14）的时候，迭代实现创建range的固定成本占总执行时间的比例很高，算下来总开销反而比递归略高；随着n变大，range的固定成本被更多次循环摊薄，递归每一层栈帧分配、函数调用的可变成本线性累加，总开销很快就超过迭代实现。两者的开销曲线交点刚好落在n=14附近——这个值根本不是什么特殊的魔法数，换个Python版本、换个CPU、换个操作系统，这个交点可能跑到n=12或者n=16，没有定值。
3. Python小整数优化的影响
   14!的计算结果是87178291200，还没到Python大整数运算的性能陡降区间，两种实现做乘法的耗时几乎没差；等n涨到20以上，大整数乘法的开销占比变高，迭代实现因为访问局部变量更快，性能优势还会进一步拉大。

要是想做准确的微秒级性能测试，别直接用time.time()单次计时，应该用timeit模块，提前关闭垃圾回收、做几轮预热再取多次运行的平均时间，才能避免单次运行的杂项干扰结果。

内容的提问来源于stack exchange，提问作者Vayun