演算法 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 介面的定義移除，因為在當前代碼中沒有使用到它，

本文來自博客園，作者：尋月隱君，轉載請注明原文鏈接：https://www.cnblogs.com/QiaoPengjun/p/17461440.html

標籤：其他

上一篇：JVM運行時資料區

下一篇：返回列表