如何将判断Ke-number的两个Python函数合并为单个递归函数？

问题回顾 #

Ke-number是范围在10≤n≤99的整数：把n的十位和个位数字作为斐波那契序列的前两项，如果后续生成的序列里包含n本身，那它就是Ke-number。比如47对应的序列是4,7,11,18,29,47，因此47是Ke-number。

原实现使用两个函数完成判断：

def ke_number(n):
 n1 = int(str(n)[0])
 n2 = int(str(n)[1])
 return n in [fib(i,n1,n2) for i in range(1,100)]


def fib(n, a, b):
  if n==0 or n==1:
    return b
  return fib(n-1, b, a+b)

现在将这两个函数合并为单个递归函数，实现如下：

改造后的递归函数 #

def is_ke_number(n):
    # 嵌套递归函数：生成斐波那契序列并检查是否包含目标数n
    def check_fib_contains(prev, curr):
        # 当前项超过n，后续只会更大，直接返回False
        if curr > n:
            return False
        # 找到目标数，返回True
        if curr == n:
            return True
        # 递归生成下一项，更新前两个序列值
        return check_fib_contains(curr, prev + curr)
    
    # 拆分输入n的十位和个位，作为斐波那契序列起始项
    tens_digit = int(str(n)[0])
    units_digit = int(str(n)[1])
    
    return check_fib_contains(tens_digit, units_digit)

思路说明 #

1. 外层函数职责：仅负责拆分输入n的十位和个位数字，作为斐波那契序列的起始两项。
2. 嵌套递归函数职责：
   • 维护斐波那契序列的前两项prev和curr
   • 每一步先判断当前项curr是否等于n，是则直接返回True
   • 如果curr已大于n，说明后续序列项只会越来越大，不可能再出现n，直接返回False
   • 否则递归调用自身，将curr作为新的prev，prev+curr作为新的curr，继续检查
3. 相比原先生成固定100项再检查的方式，这个递归版本会在找到目标或超过目标时立即终止，效率更高。

测试示例 #

print(is_ke_number(47))  # 输出 True
print(is_ke_number(12))  # 输出 False（序列1,2,3,5,8,13...无12）

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