go语言递归函数及defer
递归函数
【资料图】
简单来说,递归就是函数自己调用自己。有2种实现方式,一种是直接在自己函数中调用自己,一种是间接在自己函数中调用的其他函数中调用了自己。
递归函数需要有边界条件、递归前进段、递归返回段
递归一定要有边界条件,当边界条件不满足时,递归前进;当边界条件满足时,递归返回
func fib(n int) int { a, b := 1, 1 if n <= 2 && n > 0 { return 1 } else if n <= 0 { return 0 } for i := 2; i < n; i++ { a, b = b, a+b } return b}// 递推公式变递归func fib1(n int) int { switch { case n > 0 && n < 3: return 1 case n == 0: return 0 } return fib1(n-1) + fib1(n-2)}// 循环变递归,循环次数变成了函数调用次数func fib2(a, b, n int) int { if n < 0 { panic("nagetive") } else if n == 0 { return 0 } else if n >= 3 { a, b = b, a+b return fib2(a, b, n-1) } else { return b }}func main() { for i := 0; i < 10; i++ { fmt.Println(fib(i), fib1(i), fib2(1, 1, i)) }}斐波那契数列
在循环层次变成递归函数层次中,n相当于循环变量,b和a+b就是每次循环体中使用的值
递归效率
在上面3个斐波那契数列函数实现中,如果进行时间计算,会发现fib1()函数效率最低,因为其中进行了大量的重复计算,所以慢。fib2()函数采用了递归函数调用层次代替循环层次,效率还不错,和循环版效率差不多。 但是函数每次递归,都会有压栈,递归到最后还要销毁栈帧,也会有资源开销。
对上面fib1函数进行优化后:
func fib(n int) int { a, b := 1, 1 if n <= 2 && n > 0 { return 1 } else if n <= 0 { return 0 } for i := 2; i < n; i++ { a, b = b, a+b } return b}// 递推公式变递归func fib1(n int) int { switch { case n > 0 && n < 3: return 1 case n == 0: return 0 } return fib1(n-1) + fib1(n-2)}func fib11(n int, m map[int]int) int { switch { case n > 0 && n < 3: return 1 case n == 0: return 0 } // 查询map中是否已存在 v, ok := m[n] if ok { return v } else { v = fib11(n-1, m) + fib11(n-2, m) m[n] = v return v }}func fib12(n int, s []int) int { switch { case n > 0 && n < 3: return 1 case n == 0: return 0 } // 查询map中是否已存在 if s[n] != 0 { return s[n] } else { s[n] = fib12(n-1, s) + fib12(n-2, s) return s[n] }}// 循环变递归,循环次数变成了函数调用次数func fib2(a, b, n int) int { if n < 0 { panic("nagetive") } else if n == 0 { return 0 } else if n >= 3 { a, b = b, a+b return fib2(a, b, n-1) } else { return b }}func main() { num := 100000 start_time := time.Now() dig := fib(num) end_time := time.Now() fmt.Printf("%v fib函数用时: %v\n", dig, end_time.Sub(start_time)) // start_time = time.Now() // dig = fib1(num) // end_time = time.Now() // fmt.Printf("%v fib1函数用时: %v\n", dig, end_time.Sub(start_time)) start_time = time.Now() dig = fib2(1, 1, num) end_time = time.Now() fmt.Printf("%v fib2函数用时: %v\n", dig, end_time.Sub(start_time)) start_time = time.Now() m0 := make(map[int]int, 100) dig = fib11(num, m0) end_time = time.Now() fmt.Printf("%v fib11函数用时: %v\n", dig, end_time.Sub(start_time)) start_time = time.Now() s0 := make([]int, num+1, num+1) dig = fib12(num, s0) end_time = time.Now() fmt.Printf("%v fib12函数用时: %v\n", dig, end_time.Sub(start_time))}优化后并对比
当num为100000时,明显看出各个函数哪个效率是最高的了。fib12函数和fib11函数的不同之处是采用的缓存方式不同,由于fib12采用的是切片,fib11采用的是hash表,采用切片,省去了hash计算,节省了很多时间。
间接递归
间接递归调用,是函数通过别的函数调用了自己,这一样也是递归。 只要是递归调用,不管是直接还是间接,都需要注意边界返回问题。但是间接递归调用有时候是非常不明显,代码调用复杂时,很难发现出现了递归调用,这是非常危险的。
func foo() { bar()}func bar() { foo()}foo()
递归是一种很自然的表达,符合逻辑思维
递归相对运行效率低,每一次调用函数都要开辟栈帧
递归有深度限制,如果递归层次太深,函数连续压栈,栈内存就可能溢出了
如果是有限次数的递归,可以使用递归调用,或者使用循环代替,循环代码稍微复杂一些,但是只要不是死循环,可以多次迭代直至算出结果
绝大多数递归,都可以使用循环实现
函数嵌套
package mainimport "fmt"func outer() { c := 99 var inner = func() { fmt.Println("1 inner", c, &c) } inner() fmt.Println("2 outer", c, &c)}func main() { outer()}
到outer中定义了另外一个函数inner,并且调用了inner。outer是包级变量,main可见,可以调 用。而inner是outer中的局部变量,outer中可见。
闭包
自由变量:未在本地作用域中定义的变量。例如定义在内层函数外的外层函数的作用域中的变量。
闭包:就是一个概念,出现在嵌套函数中,指的是内层函数引用到了外层函数的自由变量,就形成了闭包。很多语言都有这个概念,最熟悉就是JavaScript。闭包是运行期动态的概念。
- 函数有嵌套,函数内定义了其它函数
- 内部函数使用了外部函数的局部变量
- 内部函数被返回(非必须)
package mainimport "fmt"func outer() func() { c := 99 fmt.Printf("outer %d %p\n", c, &c) var inner = func() { fmt.Printf("inner %d %p\n", c, &c) } return inner}func main() { var fn = outer() fn()
首先有嵌套函数,也就是有嵌套作用域,inner函数中用到了c,但是它没有定义c,而外部的outer有局部变量c。
代码分析
- 第15行调用outer函数并返回inner函数对象,并使用标识符fn记住了它。outer函数执行完了,其 栈帧上的局部变量应该释放,包括inner函数,因为它也是局部的。但是,c、inner对应的值都不 能释放,因为fn要用。所以这些值不能放在栈上,要放到堆上。在Go语言中,这称为变量逃逸,逃逸到堆上
- 在某个时刻,fn函数调用时,需要用到c,但是其内部没有定义c,它是outer的局部变量,如果这 个c早已随着outer的调用而释放,那么fn函数调用一定出现错误,所以,这个outer的c不能释放, 但是outer已经调用完成了,怎么办?闭包,让inner函数记住自由变量c(逃逸到堆上的内存地址)
defer
defer意思是推迟、延迟。语法很简单,就在正常的语句前加上defer就可以了。
在某函数中使用defer语句,会使得defer后跟的语句进行延迟处理,当该函数即将返回时,或发生 panic时,defer后语句开始执行。
注意os.Exit不是这两种情况,不会执行defer。
同一个函数可以有多个defer语句,依次加入调用栈中(LIFO),函数返回或panic时,从栈顶依次执行 defer后语句。
执行的先后顺序和注册的顺序正好相反,也就是后注册的先执行。 defer后的语句必须是一个函数或方法的调用。
下一篇:最后一页
go语言递归函数及defer
递归函数简单来说,递归就是函数自己调用自己。有2种实现方式,一种是
2023-06-276月1日-26日市场共发行绿色债券51只
6月1日-26日市场共发行绿色债券51只
2023-06-27美媒又开始放风:美财政部长耶伦计划7月初访问北京
【环球网报道】据彭博社27日报道,多名熟悉行程的消息人士透露,美国财
2023-06-27头条:上海景点英语_景点英语
1、景点featurespot,viewspot旅游景点touristattractiontouristd
2023-06-276月27日生意社二氯甲烷基准价为2400.00元/吨-热头条
6月27日,生意社二氯甲烷基准价为2400 00元 吨,与本月初(2410 00元 吨
2023-06-27环球焦点!北海哪一种海鲜最受欢迎?
海鲜清甜美味,而且营养丰富,吃海鲜最佳的地方要数海边了,暑假到北海
2023-06-27何猷君关联电竞公司增资至5亿 武汉星竞威武公司增资至5亿 当前滚动
天眼查App显示,近日,武汉星竞威武文体发展有限公司发生工商变更,注
2023-06-27哪个关于exo的贴吧最好听_哪个关于EXO的贴吧最好|世界滚动
1、亲,现在有关于EXO的许多贴吧。2、其中EXO是大吧,里面有关于EXO的
2023-06-27美国科罗拉多州夜店枪击案嫌疑人认罪 将面临终身监禁
当地时间6月26日,去年在美国科罗拉多州斯普林斯市一间夜店制造大规
2023-06-27天天热资讯!鸡子黄的功效与作用(天地混沌如鸡子 盘古生其中 hellip hellip 古文翻译)
子黄的功效与作用,天地混沌如鸡子盘古生其中helliphellip古文翻译这个
2023-06-27X 关闭
X 关闭
- 最新全国疫情中高风险地区名单:全国现有高中风险地区15+64个(统计时间:5月19日6时)
- 北京疫情最新消息|5月18日北京新增50例本土确诊病例和5例无症状感染者
- 上海疫情最新消息|5月18日上海新增本土确诊病例82例和本土无症状感染者637例
- 郑州限号|今天是2022年5月19日,郑州限行尾号是4和9
- 发码总数超68万!郑州市“场所码”覆盖精度再提升
- 郑州发布100号通告:调整封控管控区域
- 【“郑”在抗疫】郑州互联网企业开展爱心购瓜网络公益活动
- 10岁顽童因“想妈妈”爬楼顶,暖心民警化身“心理医生”解心结
- 洛阳馨悦社工:以微薄之力让社区更安全
- 平顶山新华区对4名违反疫情防控有关规定人员依法处理