如何不使用循环或平方根运算判断一个数是否属于斐波那契数列

1. 预生成查表法（最推荐） #

这是面试和实际开发中最通用的合规方案，逻辑如下：

• 常用编程语言的内置整数类型范围有限，32位有符号整数范围内仅存在47个斐波那契数，64位有符号整数范围内也只有93个，数量极少可以一次性预生成存入哈希集合
• 预生成操作是程序初始化阶段的一次性行为，不属于运行时判断逻辑的一部分，运行时仅需要判断目标值是否在集合中，完全符合无循环、无平方根的要求
  示例代码（Python）：

# 初始化阶段预生成所有64位有符号整数范围内的斐波那契数
FIB_COLLECTION = set()
prev, curr = 0, 1
MAX_INT = 2 ** 63 - 1
while prev <= MAX_INT:
    FIB_COLLECTION.add(prev)
    prev, curr = curr, prev + curr

# 运行时判断逻辑，无循环、无平方根、时间复杂度O(1)
def check_fib(num):
    return num in FIB_COLLECTION

2. 编译期预计算（适用于静态强类型语言） #

如果面试官不允许初始化阶段的预计算，可以使用C++、Rust、Java 15+等语言的编译期计算特性：

• 通过constexpr、模板元编程等能力，在编译阶段就计算好所有合法范围内的斐波那契数，生成静态查找表
• 程序运行后的判断逻辑仅包含查表操作，无任何运行时计算、循环、平方根调用

3. 递归判断（仅适用于允许递归的场景） #

如果面试官明确递归不属于题目禁止的循环范畴，可以使用递归实现：

def check_fib(num, a=0, b=1):
    if a == num:
        return True
    if a > num:
        return False
    return check_fib(num, b, a + b)

64位整数范围内斐波那契数最多只有93个，递归深度不超过93，不会触发栈溢出限制。

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