如何修改De Bruijn算法适配大数？求非递归DFS实现方案

当n=18、k=3时，原递归DFS的调用深度会达到3^18=387420489，远超Python默认的递归深度限制（默认约1000），直接触发RecursionError。将递归DFS改为非递归实现即可解决这个问题，核心是用栈模拟递归的调用和回溯过程：

修改后的完整代码 #

import math

def de_bruijn(n, k, A):
    seen = set()
    edges = []
    start_node = A[0] * (n - 1)
    
    # 用栈模拟递归，元素为(任务类型, 数据)
    # 任务类型："explore" 探索节点的边；"backtrack" 回溯添加边索引到edges
    stack = [("explore", start_node)]
    
    while stack:
        task, data = stack.pop()
        if task == "explore":
            node = data
            # 倒序遍历i，保证栈处理顺序和原递归正序遍历一致
            for i in reversed(range(k)):
                current_str = node + A[i]
                if current_str not in seen:
                    seen.add(current_str)
                    # 先压入回溯任务（递归返回后执行的操作）
                    stack.append(("backtrack", i))
                    # 再压入子节点的探索任务（递归进入子节点）
                    stack.append(("explore", current_str[1:]))
        elif task == "backtrack":
            edges.append(data)
    
    # 生成最终的De Bruijn序列
    s = ""
    sequence_length = int(math.pow(k, n))
    for i in range(sequence_length):
        s += A[edges[i]]
    s += start_node
    return s

# 测试用例
n = 18
k = 3
A = '012'
print(de_bruijn(n, k, A))

关键说明 #

1. 栈模拟递归逻辑：

   • "explore"任务对应原递归中进入节点的操作，遍历所有可能的边（i从0到k-1）
   • "backtrack"任务对应原递归中返回后的操作，将边索引添加到edges列表
   • 倒序遍历i是因为栈是后进先出结构，这样能保证边的处理顺序和原递归完全一致，生成的序列结果不变

2. 局部状态替代全局变量：
   把原代码中全局的seen和edges改为函数内的局部变量，避免多次调用函数时的状态污染，代码更健壮

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