【天天热闻】go语言递归函数及defer

手机

环球观热点：国产EDA软件领域首现深度合作合见工软与华大九天共推芯片解决方案

【环球新视野】5天一层楼！最新一代“造楼机”亮相武汉

家电

【天天热闻】go语言递归函数及defer

2023-06-27 09:55:05 来源：博客园

递归函数

简单来说，递归就是函数自己调用自己。有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后的语句必须是一个函数或方法的调用。

关键词：