调用f(0)时会打印多少个唯一数字？Python递归问题求解

• 递归深度溢出：你写的递归本质是深度优先搜索，会沿着一个分支一直往下调用，比如f(0)→f(5)→f(3)→f(1)→f(6)……递归深度随数值增长线性上升，哪怕修改了系统递归限制，Python的调用栈也承载不了上亿的深度，直接卡死无响应。
• 存在性检查效率极低：用列表做n not in lst判断的时间复杂度是O(k)，k是列表当前长度，元素越多判断越慢，程序看似无输出实际是运行速度过慢。
• 无剪枝逻辑：1e9的数值范围完全不需要全部遍历，靠数学规律可以提前终止计算。

思路1：用BFS代替递归 + 集合去重 + 提前剪枝 #

递归的本质是栈实现，换成广度优先搜索（队列实现）可以完全规避递归深度问题，用集合做去重和存在性检查，时间复杂度降到O(1)，再结合数学规律提前终止，不用遍历到1e9。

核心推导 #

1. 可生成的负数只有-1和-2：只有≥0的数才会触发子调用，n-2最多生成0-2=-2、1-2=-1两个负数，没有更小的负数。
2. 所有≥0的整数都可以生成：只要覆盖了1、2、3、4四个连续整数，后续任意整数都可以通过+5/+7生成更大值，再通过-2递推出所有中间值，奇偶性可以通过加奇数（5/7）切换，没有缺口。

代码实现 #

from collections import deque

def count_unique_numbers(max_n=10**9):
    visited = set()
    queue = deque([0])
    visited.add(0)

    while queue:
        current = queue.popleft()
        if 0 <= current <= max_n:
            for delta in (-2, 5, 7):
                next_num = current + delta
                if next_num not in visited:
                    visited.add(next_num)
                    queue.append(next_num)
        # 提前终止：确认1、2、3、4都已覆盖，后续所有≥0的数都可生成
        if {1,2,3,4}.issubset(visited):
            # ≥0的数共max_n+1个，加上2个负数
            return max_n + 1 + 2
    # 极端情况兜底（实际不会触发）
    return len(visited)

print(count_unique_numbers())

运行后直接输出结果1000000003，无性能问题。

思路2：纯数学计算 #

根据上面的推导可以直接得出结果，不需要写遍历逻辑：

• 可生成负数：2个（-1、-2）
• 可生成非负数：从0到1e9共1000000001个
• 总数：2 + 1000000001 = 1000000003

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