Paxon Qiao's Tech Blog

Go语言实战：递归算法的实现与优化

· 5min · Paxon Qiao
Table of Contents

Go语言实战：递归算法的实现与优化

递归是一种强大而灵活的算法思想，在解决问题时通过函数调用自身来实现逐步分解问题。本文通过一个模拟场景——“从套娃中寻找宝石”，详细讲解递归的概念、实现方式以及如何优化代码以提高效率和可读性。

本文聚焦于Golang中的递归算法，通过一个嵌套结构体场景（套娃查找宝石）详细说明递归的设计和实现。我们首先提供了一个基本的递归代码示例，随后对代码进行了优化，并通过详细注释讲解了改进的关键点。最终，读者将掌握递归算法在实际编程中的应用方法和优化技巧。

算法 in Golang：Recursion（递归）

递归算法

场景：在套娃中找到宝石

可以这样做

  • while 没找到：
    • if 当前项 is 宝石：
      • return 宝石
    • else if 当前项 is 套娃：
      • 打开这个套娃
      • if 当前项 is 宝石：
        • return 宝石
      • else 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。优化的话可以考虑以下几点：

  1. 可以将嵌套的Item结构体改为一个数组或切片，这样可以更方便地遍历和查找其中的元素。
  2. 可以使用递归函数来查找钻石，但是需要注意避免出现无限递归的情况。
  3. 可以将Item结构体中的Child字段改为一个指向父节点的指针，这样可以更方便地遍历整个结构体。
  4. 可以将Item结构体实现IsDiamond()方法，这样可以更方便地判断一个Item是否为钻石。
  5. 可以将ItemClassifier接口改为一个IsDiamond()方法，这样可以更方便地判断一个Item是否为钻石。

ChatGPT 优化

下面是优化后的代码：

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"
}

优化说明：

  1. 将 findDiamond 函数的参数和返回值改为 *Item 类型，以便避免不必要的内存拷贝。
  2. 将创建 Item 链的代码提取到一个单独的函数 createItemChain 中，使代码更清晰。
  3. 在 createItemChain 函数中使用指针来创建 Item 对象，以避免在函数间传递大量的数据。
  4. 修改 findDiamond 函数，使其接受 *Item 参数，以避免在递归调用时进行不必要的解引用。
  5. 修改 findDiamond 函数的递归调用，将 item.Child 直接传递给 findDiamond，而不是解引用再传递。
  6. 将 ItemClassifier 接口的定义移除，因为在当前代码中没有使用到它。

总结

递归是一种在编程中非常高效的解决问题的方式，尤其适合处理具有嵌套或分层结构的问题。在本文中，我们通过“套娃查找宝石”的递归示例，展示了递归算法的设计、实现和优化方法。总结来看，递归算法的核心在于：

  1. 基线条件（Base Case）：明确递归的终止条件，避免无限循环。
  2. 递归条件（Recursive Case）：确保问题能通过递归逐步缩小规模并最终收敛。
  3. 代码优化：通过参数传递方式和逻辑拆分，减少不必要的资源消耗和复杂度。

希望通过本文的讲解，读者能够将递归思想灵活运用于Golang开发中，从而提升编程能力。

Categories Go
Tags Go