pattern(k)函数规律识别与递归实现方法咨询

拆解给出的示例输出后，可以明确以下递归规律：

• 基础情况：当k=0或k=1时，结果固定为字符串"1"
• 递归情况：当k≥2时，pattern(k)由三部分拼接而成：
  1. pattern(k-1)的结果
  2. 连续k个字符"0"
  3. pattern(k-2)的结果

验证所有示例：

• pattern(2) = pattern(1) + "00" + pattern(0) = "1"+"00"+"1" = "1001" ✔️
• pattern(3) = pattern(2) + "000" + pattern(1) = "1001"+"000"+"1" = "10010001" ✔️
• pattern(4) = pattern(3) + "0000" + pattern(2) = "10010001"+"0000"+"1001" = "1001000100001001" ✔️
• pattern(5) = pattern(4) + "00000" + pattern(3) = "1001000100001001"+"00000"+"10010001" = "10010001000010010000010010001" ✔️

基础递归实现 #

直接按照上述规律编写递归函数，终止条件为k≤1时返回"1"：

def pattern(k):
    if k <= 1:
        return "1"
    return pattern(k-1) + "0" * k + pattern(k-2)

优化版（带缓存） #

基础递归会重复计算大量子问题（比如pattern(k-2)会被pattern(k)和pattern(k-1)多次调用），用缓存可以避免重复计算，大幅提升大k值场景下的效率：

from functools import lru_cache

@lru_cache(maxsize=None)
def pattern(k):
    if k <= 1:
        return "1"
    return pattern(k-1) + "0" * k + pattern(k-2)

测试验证 #

运行题目给出的测试代码：

for k in range(0,6):
    print("pattern("+str(k)+"): " + pattern(k))

输出与题目示例完全一致。

内容的提问来源于stack exchange，提问作者Hazem El Sankari