Go語言遞迴函數的具體實現

2023-04-04 06:00:56

很對程式語言都支援遞迴函數，Go語言也不例外，所謂遞迴函數指的是在函數內部呼叫函數自身的函數，從數學解題思路來說，遞迴就是把一個大問題拆分成多個小問題，再各個擊破，在實際開發過程中，遞迴函數可以解決許多數學問題，如計算給定數位階乘、產生斐波系列等。

構成遞迴需要具備以下條件：

一個問題可以被拆分成多個子問題；
拆分前的原問題與拆分後的子問題除了資料規模不同，但處理問題的思路是一樣的；
不能無限制的呼叫本身，子問題需要有退出遞迴狀態的條件。

注意：編寫遞迴函數時，一定要有終止條件，否則就會無限呼叫下去，直到記憶體溢位。

下面通過幾個範例來演示一下遞迴函數的使用。

斐波那契數列

下面我們就以遞迴函數的經典範例 —— 斐波那契數列為例，演示如何通過Go語言編寫的遞迴函數來列印斐波那契數列。

數列的形式如下所示：

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …

使用Go語言遞迴函數實現斐波那契數列的具體程式碼如下所示：

package main
import "fmt"
func main() {
    result := 0
    for i := 1; i <= 10; i++ {
        result = fibonacci(i)
        fmt.Printf("fibonacci(%d) is: %dn", 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

數位階乘

一個正整數的階乘（factorial）是所有小於及等於該數的正整數的積，並且 0 的階乘為 1，自然數 n 的階乘寫作n!，“基斯頓·卡曼”在 1808 年發明了n!這個運運算元號。

例如，n!=1×2×3×…×n，階乘亦可以遞迴方式定義：0!=1，n!=(n-1)!×n。

使用遞迴函數計算給定數的階乘，範例程式碼如下所示：

package main
import "fmt"
func Factorial(n uint64) (result uint64) {
    if n > 0 {
        result = n * Factorial(n-1)
        return result
    }
    return 1
}
func main() {
    var i int = 10
    fmt.Printf("%d 的階乘是 %dn", i, Factorial(uint64(i)))
}

輸出結果為：

10 的階乘是 3628800

多個函陣列成遞迴

Go語言中也可以使用相互呼叫的遞迴函數，多個函數之間相互呼叫形成閉環，因為Go語言編譯器的特殊性，這些函數的宣告順序可以是任意的，下面這個簡單的例子展示了函數 odd 和 even 之間的相互呼叫：

package main
import (
    "fmt"
)
func main() {
    fmt.Printf("%d is even: is %tn", 16, even(16)) // 16 is even: is true
    fmt.Printf("%d is odd: is %tn", 17, odd(17))
    // 17 is odd: is true
    fmt.Printf("%d is odd: is %tn", 18, odd(18))
    // 18 is odd: is false
}
func even(nr int) bool {
    if nr == 0 {
        return true
    }
    return odd(RevSign(nr) - 1)
}
func odd(nr int) bool {
    if nr == 0 {
        return false
    }
    return even(RevSign(nr) - 1)
}
func RevSign(nr int) int {
    if nr < 0 {
        return -nr
    }
    return nr
}

執行效果如下所示：

16 is even: is true
17 is odd: is true
18 is odd: is false

到此這篇關於Go語言遞迴函數的具體實現的文章就介紹到這了,更多相關Go語言遞迴函數內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Go語言遞迴函數的具體實現

目錄

斐波那契數列

數位階乘

多個函陣列成遞迴

熱門文章