Python Lambda递归超1e5次触发Segmentation Fault问题排查

问题背景 #

你实现了用于统计1到N中满足二元谓词条件数字数量的count_cond函数：Lambda递归版本在小规模测试中正常运行，但处理大规模数据（如count_factors(100000)）时触发Segmentation Fault崩溃；而等价的普通递归函数即使处理1e7级别的数据仍能正常执行。

Lambda递归实现代码：

def count_cond(condition):
    return lambda x:(((lambda f:(lambda a:f(a(a)))(lambda a:f(lambda *w:a(a)(*w))))(lambda cc: lambda j,m: ((cc(j+1,m+1) if condition(x,m)==True else cc(j,m+1))) if m<=x else j))(0,1))
# Returns a function with one parameter N that counts all the numbers from 1 to N that satisfy the two-argument predicate function Condition, where the first argument for Condition is N and the second argument is the number from 1 to N.

普通递归实现代码：

def cc(condition,x,j=0,m=1):
    return ((cc(condition,x,j+1,m+1) if condition(x,m)==True else cc(condition,x,j,m+1))) if m<=x else j

原因分析 #

这是Python对匿名函数（Lambda）与嵌套递归的处理特性导致的：

• Lambda版本使用Y组合子实现递归，每一层递归都会创建新的Lambda闭包，这些闭包会持有外层作用域的变量（如x、condition）。随着递归深度增加，内存中会堆积大量闭包实例，其内存开销远大于普通递归函数。
• 普通递归函数是直接调用自身，Python的递归栈管理对函数对象的复用更高效，不会产生额外的闭包内存负担。即使设置sys.setrecursionlimit提升递归深度上限，Lambda版本的闭包内存占用仍会快速耗尽进程地址空间，最终触发Segmentation Fault。

修复方案 #

方案一：改用迭代实现（推荐） #

完全规避递归栈和闭包内存问题，效率最高，适合处理任何规模的数据：

def count_cond(condition):
    def counter(x):
        count = 0
        for m in range(1, x+1):
            if condition(x, m):
                count += 1
        return count
    return counter

方案二：调整Lambda递归的变量持有方式 #

如果坚持使用Lambda风格，将x作为参数传入递归逻辑，避免闭包持有x的引用，减少内存开销：

def count_cond(condition):
    return lambda x: (
        (lambda f: (lambda a: f(a(a)))(lambda a: f(lambda *w: a(a)(*w))))
        (lambda cc: lambda x_val, j, m: 
            cc(x_val, j+1, m+1) if condition(x_val, m) else cc(x_val, j, m+1) 
            if m <= x_val else j
        )(x, 0, 1)
    )

注：该方式仍依赖递归栈，大规模数据下仍可能受限于递归深度上限。

方案三：手动模拟递归栈 #

用列表模拟递归栈，既保留递归逻辑结构，又避免Python默认递归栈的限制：

def count_cond(condition):
    def counter(x):
        stack = [(x, 0, 1)]
        result = 0
        while stack:
            x_val, j, m = stack.pop()
            if m > x_val:
                result = j
                continue
            if condition(x_val, m):
                stack.append((x_val, j+1, m+1))
            else:
                stack.append((x_val, j, m+1))
        return result
    return counter

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