了解回溯

Question

def bitstr(n,s):
    if n==1:return s
    return[digit+ bits for digit in bitstr(1,s) for bits in bitstr(n-1,s)]
print(bitstr(3,'abc'))

请说明这段代码中发生了什么。回溯如何进行？

Answer 1

由于巨大的return语句，因此很难理解此代码。

基本上，除非达到终止条件，否则在所有情况下都将递归。所有回溯只是具有特定终止条件的深度优先搜索。

考虑在迷宫中穿行，在每个步骤中您都要做出决定，该决定就是对调用堆栈的调用（执行您的深度优先搜索）...如果到达终点，则可以返回路径。但是，如果达到死胡同，则想退出某个决定，实质上就是退出调用堆栈中的函数。

因此，当我想到回溯时，我会在意

1. 状态
2. 决定
3. 基本案例（终止条件）

我在回溯here的视频中对此进行了解释。