请问这两种写法为什么结果不一样？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

最近在刷题，有一段代码如果写成下面这样结果就是对的

func foo(i, j int) bool {

    ret1 := foo(i+1, j)
    ret2 := foo(i-1, j)
    ret3 := foo(i, j+1) 
    ret4 := foo(i, j-1)

    return ret1 && ret2 && ret3 && ret4
}

但是如果写成这样，某些 test case 结果就错

func foo(i, j int) bool {

    return foo(i+1, j) && foo(i-1, j) && foo(i, j+1) && foo(i, j-1)
}

想不明白啊，这两种写法哪里不一样了？

第 1 条附言 · 8 小时 10 分钟前

回答二楼的问题，foo() 函数里面会改变一些值，我写上更加完整的吧,

func foo(g [][]int, v [][]bool, i, j int) bool {

    ret1 := foo(g, v, i+1, j)
    ret2 := foo(g, v, , i-1, j)
    ret3 := foo(g, v, i, j+1) 
    ret4 := foo(g, v, i, j-1)

    return ret1 && ret2 && ret3 && ret4
}

func foo(g [][]int, v [][]bool, i, j int) bool {

    return foo(g, v, i+1, j) && foo(g, v,  i-1, j) && foo(g, v, i, j+1) && foo(g,v, i, j-1)
}

执行过程中会对 v[i][j] 的值进行修改

7 条回复 • 2024-11-07 19:14:35 +08:00

pweng286

8 小时 47 分钟前

AI
关键区别：
递归调用顺序：

在第一段代码中，foo 被分别递归调用并赋值给 ret1, ret2, ret3, ret4 。这意味着所有的递归调用会按顺序执行，一个接一个。如果在某个递归过程中返回了 false ，其余的递归调用仍然会继续执行，但最终的返回值是 ret1 && ret2 && ret3 && ret4 ，即它会检查所有递归的结果。

在第二段代码中，所有的递归调用都在一个单一的布尔表达式中同时执行。这意味着 foo(i+1, j) && foo(i-1, j) && foo(i, j+1) && foo(i, j-1) 会在一开始就并行执行（实际上是按照顺序依赖 && 操作符的短路性质）。短路运算意味着如果第一个调用（例如 foo(i+1, j)）返回 false ，那么剩下的递归调用会被立即跳过，并且整个表达式会立刻返回 false ，不会继续执行其他递归调用。

短路特性：

在第二段代码中，&& 是一个短路操作符，也就是说，当第一个 foo(i+1, j) 返回 false 时，后续的 foo(i-1, j), foo(i, j+1), foo(i, j-1) 会被跳过，因此可能会导致在某些情况下，代码没有完整地执行所有递归调用，可能会错过一些重要的逻辑判断。

而在第一段代码中，由于每个递归调用是逐个进行的，即使某些调用的返回值是 false ，后续的递归调用仍会被执行，所以你可以确保每次递归的每一个方向都被检查。

为什么第二种写法会错误：
如果你的递归逻辑依赖于每个方向（ i+1, i-1, j+1, j-1 ）的返回值，那么在第二段代码中，短路机制可能导致部分方向没有被检查到。例如：

假设 foo(i+1, j) 返回 false ，根据短路原则，后面的 foo(i-1, j)、foo(i, j+1)、foo(i, j-1) 就不会执行了。因此，可能漏掉了一些重要的判断，导致最终结果不正确。
而在第一种写法中，虽然某个方向可能返回 false ，但是所有的递归都会执行，确保每个方向都被遍历，从而保证递归的正确性。

总结：
第一段代码按顺序递归调用每个方向，确保所有的递归都被执行，因此不会错过任何重要的检查。
第二段代码在使用短路操作符时，一旦某个递归返回 false ，后续的递归就不会继续进行，可能导致遗漏重要的判断逻辑，从而造成错误。
因此，如果你的递归逻辑需要检查所有的方向，那么你应该使用第一种写法，逐个递归调用每个方向。