go语言递归函数及defer-526互联

递归函数

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