算法 in Golang:Recursion(递归)
递归算法
场景:在套娃中找到宝石
可以这样做
- while 没找到:
- if 当前项 is 宝石:
- return 宝石
- else if 当前项 is 套娃:
- 打开这个套娃
- if 当前项 is 宝石:
- return 宝石
- else if 当前项 is 套娃:
- 打开这个套娃
- if 当前项 is 宝石:
- ... ...
- if 当前项 is 宝石:
递归
- 打开套娃
- 找到的是宝石,结束
- 得到的是一个套娃(重复操作,再次打开套娃,进行判断...)
递归术语解释
- 递归 Recursion
- 基线条件 Base Case
- 递归条件 Recursive Case
创建递归算法项目文件夹,并初始化用VSCode打开
~/Code/go via 🐹 v1.20.3 via 🅒 base
➜ mcd recursion_demo
Code/go/recursion_demo via 🐹 v1.20.3 via 🅒 base
➜ go mod init recursion_demo
go: creating new go.mod: module recursion_demo
Code/go/recursion_demo via 🐹 v1.20.3 via 🅒 base
➜ c
Code/go/recursion_demo via 🐹 v1.20.3 via 🅒 base
➜
代码:
package main
import "fmt"
func main() {
doll := Item{
ID: 1,
Type: "doll",
Child: &Item{
ID: 2,
Type: "doll",
Child: &Item{
ID: 3,
Type: "doll",
Child: &Item{
ID: 4,
Type: "diamond",
Child: nil,
},
},
},
}
diamond := findDiamond(doll)
fmt.Printf("Item %d is diamond\n", diamond.ID)
}
func findDiamond(item Item) Item {
if item.IsDoll() {
return findDiamond(*item.Child)
} else {
return item
}
}
type Item struct {
ID int
Type string
Child *Item
}
type ItemClassifier interface {
IsDoll() bool
}
func (it *Item) IsDoll() bool {
if it.Type == "doll" {
return true
}
return false
}
运行
Code/go/recursion_demo via 🐹 v1.20.3 via 🅒 base
➜ go run .
Item 4 is diamond
Code/go/recursion_demo via 🐹 v1.20.3 via 🅒 base
➜
优化
package main
import "fmt"
func main() {
doll := Item{
ID: 1,
Type: "doll",
Child: &Item{
ID: 2,
Type: "doll",
Child: &Item{
ID: 3,
Type: "doll",
Child: &Item{
ID: 4,
Type: "diamond",
Child: nil,
},
},
},
}
diamond := findDiamond(doll)
fmt.Printf("Item %d is diamond\n", diamond.ID)
}
func findDiamond(item Item) Item {
if item.IsDoll() {
return findDiamond(*item.Child)
} else {
return item
}
}
type Item struct {
ID int
Type string
Child *Item
}
type ItemClassifier interface {
IsDoll() bool
}
func (it *Item) IsDoll() bool {
return it.Type == "doll"
}
vscode ChatGPT优化解释:
这段代码的主要功能是查找一个嵌套的Item结构体中的钻石,并输出其ID。优化的话可以考虑以下几点:
- 可以将嵌套的Item结构体改为一个数组或切片,这样可以更方便地遍历和查找其中的元素。
- 可以使用递归函数来查找钻石,但是需要注意避免出现无限递归的情况。
- 可以将Item结构体中的Child字段改为一个指向父节点的指针,这样可以更方便地遍历整个结构体。
- 可以将Item结构体实现IsDiamond()方法,这样可以更方便地判断一个Item是否为钻石。
- 可以将ItemClassifier接口改为一个IsDiamond()方法,这样可以更方便地判断一个Item是否为钻石。
ChatGPT 优化:
下面是优化后的代码:文章来源:https://www.toymoban.com/news/detail-473490.html
package main
import "fmt"
func main() {
doll := createItemChain()
diamond := findDiamond(doll)
fmt.Printf("Item %d is diamond\n", diamond.ID)
}
func createItemChain() *Item {
doll := &Item{
ID: 1,
Type: "doll",
}
doll.Child = &Item{
ID: 2,
Type: "doll",
}
doll.Child.Child = &Item{
ID: 3,
Type: "doll",
}
doll.Child.Child.Child = &Item{
ID: 4,
Type: "diamond",
}
return doll
}
func findDiamond(item *Item) *Item {
if item.IsDoll() {
return findDiamond(item.Child)
}
return item
}
type Item struct {
ID int
Type string
Child *Item
}
func (it *Item) IsDoll() bool {
return it.Type == "doll"
}
优化说明:文章来源地址https://www.toymoban.com/news/detail-473490.html
- 将
findDiamond
函数的参数和返回值改为*Item
类型,以便避免不必要的内存拷贝。 - 将创建
Item
链的代码提取到一个单独的函数createItemChain
中,使代码更清晰。 - 在
createItemChain
函数中使用指针来创建Item
对象,以避免在函数间传递大量的数据。 - 修改
findDiamond
函数,使其接受*Item
参数,以避免在递归调用时进行不必要的解引用。 - 修改
findDiamond
函数的递归调用,将item.Child
直接传递给findDiamond
,而不是解引用再传递。 - 将
ItemClassifier
接口的定义移除,因为在当前代码中没有使用到它。
到了这里,关于算法 in Golang:Recursion(递归)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!