V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
n0bug
V2EX  ›  问与答

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

  •  
  •   n0bug · 6 小时 48 分钟前 · 513 次点击

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

    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 条附言  ·  6 小时 9 分钟前

    回答二楼的问题,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
        1
    pweng286  
       6 小时 46 分钟前
    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 ,后续的递归就不会继续进行,可能导致遗漏重要的判断逻辑,从而造成错误。
    因此,如果你的递归逻辑需要检查所有的方向,那么你应该使用第一种写法,逐个递归调用每个方向。
    CEBBCAT
        2
    CEBBCAT  
       6 小时 44 分钟前
    内嵌的那个 foo 有状态吗?
    n0bug
        3
    n0bug  
    OP
       6 小时 9 分钟前
    @CEBBCAT 会的,我更新了一下问题
    CSM
        4
    CSM  
       6 小时 5 分钟前
    zapper
        5
    zapper  
       5 小时 57 分钟前
    @pweng286 #1 请不要把 AI 生成的内容发送到这里
    https://www.v2ex.com/about
    sqfphoenix
        6
    sqfphoenix  
       5 小时 47 分钟前
    第二种写法前面某一个 foo 返回 false 了,之后的 foo 都不会执行了
    pweng286
        7
    pweng286  
       4 小时 33 分钟前
    @zapper 好的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2520 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 20ms · UTC 15:47 · PVG 23:47 · LAX 07:47 · JFK 10:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.