算法 in Golang:Recursion(递归)

这篇具有很好参考价值的文章主要介绍了算法 in Golang:Recursion(递归)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

优化说明:文章来源地址https://www.toymoban.com/news/detail-473490.html

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

到了这里,关于算法 in Golang:Recursion(递归)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法 in Golang:Breadth-first search(BFS、广度优先搜索)

    从 A 到 F 点有多条路径 将问题建模为图(Graph) 通过 Breadth-first Search 算法来解决问题 图是用来对不同事物间如何关联进行建模的一种方式 图是一种数据结构 作用于图(Graph) 能够回答两类问题: 是否能够从节点 A 到节点 B? 从 A 到 B 的最短路径是什么? 直接添加的朋友

    2024年02月08日
    浏览(42)
  • 数据结构 in Golang:Hash Tables(哈希表)

    水果店的价格表: 苹果 Apple:3元 香蕉 Banana:4元 桃子 Peach:2元 梨 Pear:3元 找到一种水果的价格: 可以使用 binary search,通过名称来查找,耗时:O(logn) 如何只耗时 O(1) 来找到价格呢? Hash 函数:通过一个字符串 - 一个数值 例如: \\\"Apple\\\" - 1 \\\"Banana\\\" - 2 \\\"Peach\\\" - 7 \\\"Pear\\\" - 8 将字符

    2024年02月08日
    浏览(63)
  • 递归、搜索与回溯算法(专题一:递归)

    往期文章(希望小伙伴们在看这篇文章之前,看一下往期文章) (1)递归、搜索与回溯算法(专题零:解释回溯算法中涉及到的名词)【回溯算法入门必看】-CSDN博客 接下来我会用几道题,来让同学们利用我在专题零中提到的 递归的宏观思想 来解决这些题目。 目录 1. 汉诺

    2024年01月25日
    浏览(43)
  • 快速排序算法的递归和非递归

    基本思路 选择一个基准值,将数组划分三个区域,小于基准值的区域位于左侧,等于基准值的区域位于中间,大于基准值的区域位于右侧。将大于和小于区域继续进行分区,周而复始,不断进行分区和交换,直到排序完成 递归 思路: 步骤1: 在当前分区范围[l,r]中随机选中一

    2024年02月09日
    浏览(47)
  • 排序算法:归并排序(递归和非递归)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关排序算法的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 ​ 目录 1.归并排序

    2024年02月07日
    浏览(37)
  • 【Golang map并发报错】panic: assignment to entry in nil map

    go并发写 map[string]interface{} 数据的时候,报错: panic: assignment to entry in nil map 多个key同时操作一个map时,如: test[key1] = 1 test[key2] = \\\"a\\\" test[key3] = true 就会遇到并发nil值报错,什么test[key-xxx] = make()根本不行。 用异步sync.Map解决: Lock锁那个比较麻烦,不建议使用。推荐使用sync

    2024年01月19日
    浏览(33)
  • 递归以及斐波那契数列递归算法和迭代算法的实现与分析

    程序调用自身的编程技巧称为递归( recursion) 递归有两个过程,简单地说一个是 递的过程 ,一个是 归的过程 。 递归的两个必要条件 1. 存在限制条件 ,当满足这个限制条件的时候,递归便不再继续。 2.每次递归调用之后越来越 接近这个限制条件 . 递归本质就是函数调用

    2024年02月12日
    浏览(37)
  • 【算法专题】递归算法

    在解决⼀个规模为 n 的问题时,如果满足以下条件,我们可以使用递归来解决: 问题可以被划分为规模更小的子问题,并且这些子问题具有与原问题相同的解决⽅法。 当我们知道规模更小的子问题(规模为 n - 1)的解时,我们可以直接计算出规模为 n 的问题的解。 存在⼀种

    2024年02月03日
    浏览(37)
  • 08. 算法之递归算法

    递归,字面意思是递出去,拿回来,通过不断递过去,拿回来的过程,将每次调用结果保存起来,最后实现循环调用。递归在某些情况下会极大降低我们编程的复杂度。是软件开发工程师一定要掌握的技能。 递归:在数学与计算机科学中,是指在函数的定义中使用函数自身的

    2024年02月06日
    浏览(85)
  • 快速排序算法(递归非递归,三种方法实现,优化)

    快速排序 代码实现 ⚪单趟排序 版本一 ⚪快速排序 递归 关于快排优化 ⚪单趟排序 版本二 ⚪单趟排序 版本三 ⚪快速排序 非递归 特性总结 快速排序作为效率相对较高的排序,分别有递归与非递归两种写法,但都是 进行单趟排序,随后再解决其余问题。 快速排序的平均时间

    2024年02月05日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包