Golang中递归函数如何实现

Golang中递归函数如何实现 这种情况是如何发生的？我应该关注什么？

我有一个递归函数 play(b)，它传递一个结构体作为参数，在函数内部称为 bIn。

bNew 有两个切片 s 和 w。这些切片是小型结构体 c 的切片，c 包含 string1、string2 和 bool 作为其成员。

play(bIn) 中包含以下代码：

bNew := mm(bIn)
bOrigIn := bIn
play(bNew)

这是函数中唯一调用 play 的地方。

好了，铺垫够了，现在的问题是：在递归的某个时刻，比如第 23 层，调用了 play 并继续向下递归了 10 层。然后返回到第 23 层。此时，bIn 与调用前不同了。奇怪的是，bOrigIn 也与之前不同了，其变化与 bIn 中观察到的完全相同。而 bNew 则与调用前一样。

我的问题是，这怎么可能发生？所有三个变量都是函数作用域级别的，而非包级别的。

关于 bIn 变化的更多信息：切片 s 和 w 的长度都是 9。bIn 的切片 w 返回时，其第 9 个元素与离开时不同了？

现在我知道，在第 23 层到第 33 层之间的某个时刻，w 的第 9 个元素被更改为等于 s 的第 9 个元素，但布尔值被翻转，并且 s 的第 9 个元素被移除了。这个更改是由一个名为 mm(bIn) 的函数完成的。

具体来说，返回到第 23 层时，bIn 的值中 s 与原始值相同，但 w 如上段所述，即 w[8]=s[8] 且布尔值被翻转。

我怀疑这与切片的切片实际上指向与原始切片相同的内存位置有关。这似乎是解释为什么 bIn 和 bOrigIn 有相同变化的唯一原因。但是，bIn 怎么可能与调用前有任何不同呢？

感谢您阅读所有这些内容。

有什么特别需要注意的地方吗？我是否不理解 bOrigIn:=bIn 这段代码执行时发生了什么？我已经尝试过 := 和仅使用 =（在首先创建了 bOrigIn 之后）。


更多关于Golang中递归函数如何实现的实战教程也可以访问 https://www.itying.com/category-94-b0.html

3 回复

我不明白你在说什么，你能写一个示例代码吗？看代码比看文字更能清楚地了解问题所在。

更多关于Golang中递归函数如何实现的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


你说得对——我重新思考了这个问题，并用示例代码重写了我的提问。请参阅 Go - 我原以为Go是一门按值调用的语言

在Go语言中，递归函数处理结构体切片时出现这种问题，通常是由于切片底层数组共享导致的。当你传递结构体时，如果结构体包含切片字段，这些切片字段实际上是指向底层数组的引用。

问题分析

根据你的描述，关键问题在于：

  1. bIn 是函数参数（值传递）
  2. bOrigIn := bIn 创建了结构体的浅拷贝
  3. 切片字段 s 和 w 在拷贝后仍然指向相同的底层数组

示例代码演示

package main

import "fmt"

type c struct {
    string1 string
    string2 string
    boolVal bool
}

type b struct {
    s []c
    w []c
}

func mm(bIn b) b {
    // 假设这个函数修改了切片内容
    if len(bIn.s) > 0 && len(bIn.w) > 0 {
        // 这里直接修改了底层数组
        bIn.w[len(bIn.w)-1] = bIn.s[len(bIn.s)-1]
        bIn.w[len(bIn.w)-1].boolVal = !bIn.w[len(bIn.w)-1].boolVal
        bIn.s = bIn.s[:len(bIn.s)-1] // 移除最后一个元素
    }
    return bIn
}

func play(bIn b) {
    fmt.Printf("进入 play, bIn.w[8]=%v\n", bIn.w[8])
    
    bNew := mm(bIn)
    bOrigIn := bIn // 这里是浅拷贝！
    
    // 递归调用
    // play(bNew)
    
    fmt.Printf("退出 play, bIn.w[8]=%v\n", bIn.w[8])
    fmt.Printf("bOrigIn.w[8]=%v\n", bOrigIn.w[8])
    fmt.Printf("bNew.w[8]=%v\n", bNew.w[8])
}

func main() {
    // 初始化数据
    var s, w []c
    for i := 0; i < 9; i++ {
        s = append(s, c{string1: fmt.Sprintf("s%d", i), boolVal: true})
        w = append(w, c{string1: fmt.Sprintf("w%d", i), boolVal: false})
    }
    
    bIn := b{s: s, w: w}
    play(bIn)
}

关键问题解释

  1. 切片共享问题：
bOrigIn := bIn

这行代码创建了结构体的浅拷贝。虽然 bOrigIn 和 bIn 是不同的结构体实例，但它们的切片字段 s 和 w 指向相同的底层数组。

  1. mm() 函数的影响： 当 mm(bIn) 被调用时，它接收的是 bIn 的副本，但副本中的切片仍然指向相同的底层数组。如果 mm() 修改了切片的内容，这些修改会反映到原始数据中。

  2. 解决方案：深度拷贝

func deepCopyB(src b) b {
    dst := b{}
    
    // 深度拷贝 s 切片
    if src.s != nil {
        dst.s = make([]c, len(src.s))
        copy(dst.s, src.s)
    }
    
    // 深度拷贝 w 切片
    if src.w != nil {
        dst.w = make([]c, len(src.w))
        copy(dst.w, src.w)
    }
    
    return dst
}

func playFixed(bIn b) {
    bNew := mm(bIn)
    bOrigIn := deepCopyB(bIn) // 使用深度拷贝
    
    // 现在 bOrigIn 是真正的独立副本
    // play(bNew)
}
  1. 另一种方案：在 mm() 函数中创建副本
func mmSafe(bIn b) b {
    // 创建副本
    result := b{
        s: make([]c, len(bIn.s)),
        w: make([]c, len(bIn.w)),
    }
    copy(result.s, bIn.s)
    copy(result.w, bIn.w)
    
    // 修改副本
    if len(result.s) > 0 && len(result.w) > 0 {
        result.w[len(result.w)-1] = result.s[len(result.s)-1]
        result.w[len(result.w)-1].boolVal = !result.w[len(result.w)-1].boolVal
        result.s = result.s[:len(result.s)-1]
    }
    
    return result
}

需要特别注意的点

  • Go语言中结构体的值传递会拷贝所有字段，但切片、映射、通道等引用类型只会拷贝引用
  • 使用 copy() 函数可以创建切片的独立副本
  • 递归函数中修改共享数据会导致不可预期的副作用
  • 调试时可以使用 fmt.Printf("%p\n", &slice[0]) 检查切片底层数组地址是否相同

你的观察是正确的：bIn 和 bOrigIn 的变化相同是因为它们共享相同的切片底层数组。解决方案是确保在需要独立副本时进行深度拷贝。

回到顶部