【18】Go语言递归函数

在函数内部，可以调用其他函数。如果一个函数在内部调用自身，那么这个函数就是递归函数。
递归函数必须满足以下两个条件。
（1）在每一次调用自己时，必须是（在某种意义上）更接近于解。
（2）必须有一个终止处理或计算的准则。
例：阶乘

package main

import "fmt"

func main() {
    fmt.Println(factorial(5))
    fmt.Println(getMultiple(5))
}
//通过递归实现阶乘
func factorial(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorial(n-1)
}
//通过循环实现递归
func getMultiple(num int) (result int) {
    result = 1
    for i := 1; i <= num; i++ {
        result *= i
    }
    return
}

例：斐波那契数列

package main
import "fmt"
func main() {
    result := 0
    for i := 1; i <= 10; i++ {
        result = fibonacci(i)
        fmt.Printf("fibonacci(%d) is: %d\n", i, result)
    }
}
func fibonacci(n int) (res int) {
    if n <= 2 {
        res = 1
    } else {
        res = fibonacci(n-1) + fibonacci(n-2)
    }
    return
}

输出结果为：

fibonacci(1) is: 1
fibonacci(2) is: 1
fibonacci(3) is: 2
fibonacci(4) is: 3
fibonacci(5) is: 5
fibonacci(6) is: 8
fibonacci(7) is: 13
fibonacci(8) is: 21
fibonacci(9) is: 34
fibonacci(10) is: 55

Go语言中也可以使用相互调用的递归函数，多个函数之间相互调用形成闭环，因为Go语言编译器的特殊性，这些函数的声明顺序可以是任意的.
使用递归需要注意如下事项。
• 递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以用循环的方式实现，但循环的逻辑不如递归清晰。
• 使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层，每当函数返回，栈就会减一层。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。
• 使用递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。