回溯如何在编程语言中工作?

Question

我使用递归回溯，我已经使用了多个递归调用

我的代码片段:-

func test(currentIndex: Int, op: inout [Int]) {
if currentIndex > 1 {
print("exit here**********************")
return
}
print("##before", currentIndex)
test(currentIndex: currentIndex+1, op: &op)
print("after------------------------------------------------------", currentIndex)
test(currentIndex: currentIndex+1, op: &op)
print("^^^Final ================  ", currentIndex)
}
var op1: [Int] = []
test(currentIndex: 0, op: &op1)

打印->

##before 0
##before 1
exit here**********************
after------------------------------------------------------ 1
exit here**********************
^^^Final ================   1
after------------------------------------------------------ 0
##before 1
exit here**********************
after------------------------------------------------------ 1
exit here**********************
^^^Final ================   1
^^^Final ================   0

我看不懂最后4个print语句

Answer 1

你有:

func test(currentIndex: Int, op: inout [Int]) {
if currentIndex > 1 {
print("exit here**********************")
return
}
print("##before", currentIndex)
test(currentIndex: currentIndex+1, op: &op) //First
print("after------------------------------------------------------", currentIndex)
test(currentIndex: currentIndex+1, op: &op) //Second
print("^^^Final ================  ", currentIndex)
}
var op1: [Int] = []
test(currentIndex: 0, op: &op1)

让我们手动分析启动测试的最后一行正在做什么。我们将复制/粘贴代码，因为我们正在调试，如果我们手动编写所有的行。我用缩进来保持清晰。它正在制造"痕迹"。

//Index is 0:
if currentIndex > 1 {} //Skipped
print("##before", currentIndex)
test(currentIndex: currentIndex+1, op: &op) //First
//Index is 1
if currentIndex > 1 {} //Skipped
print("##before", currentIndex)
test(currentIndex: currentIndex+1, op: &op) //First
//Index is 2
if currentIndex > 1 {
print("exit here**********************")
return
}
print("after------------------------------------------------------", currentIndex)
test(currentIndex: currentIndex+1, op: &op)  //Second
//Index is 2
if currentIndex > 1 {
print("exit here**********************")
return
}
print("^^^Final ================  ", currentIndex)
print("after------------------------------------------------------", currentIndex)
test(currentIndex: currentIndex+1, op: &op) //Second
//Index is 1
if currentIndex > 1 {} //Skipped
print("##before", currentIndex)
test(currentIndex: currentIndex+1, op: &op) //First
//Index is 2
if currentIndex > 1 {
print("exit here**********************")
return
}
print("after------------------------------------------------------", currentIndex)
test(currentIndex: currentIndex+1, op: &op)  //Second
//Index is 2
if currentIndex > 1 {
print("exit here**********************")
return
}
print("^^^Final ================  ", currentIndex)
print("^^^Final ================  ", currentIndex) 

得到:

##before 0 
##before 1 
exit here**********************
after------------------------------------------------------ 1
exit here********************** 
^^^Final ================   1
after------------------------------------------------------ 0
##before 1
exit here**********************
after------------------------------------------------------ 1
exit here**********************
^^^Final ================   1
^^^Final ================   0

您也可以使用调试器，设置断点，参见callstack…