当前位置:首页> 滚动 >

go语言递归函数及defer

时间:2023-06-27 10:14:47    来源:博客园

递归函数


【资料图】

简单来说,递归就是函数自己调用自己。有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-27

6月1日-26日市场共发行绿色债券51只

6月1日-26日市场共发行绿色债券51只

2023-06-27

美媒又开始放风:美财政部长耶伦计划7月初访问北京

【环球网报道】据彭博社27日报道,多名熟悉行程的消息人士透露,美国财

2023-06-27

头条:上海景点英语_景点英语

1、景点featurespot,viewspot旅游景点touristattractiontouristd

2023-06-27

6月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-27