快捷導(dǎo)航

Go語言遞歸函數(shù)的具體實(shí)現(xiàn)

更新時(shí)間：2023年04月03日 15:24:59 作者：C語言中文網(wǎng)

本文主要介紹了Go語言遞歸函數(shù)的具體實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

很對(duì)編程語言都支持遞歸函數(shù)，Go語言也不例外，所謂遞歸函數(shù)指的是在函數(shù)內(nèi)部調(diào)用函數(shù)自身的函數(shù)，從數(shù)學(xué)解題思路來說，遞歸就是把一個(gè)大問題拆分成多個(gè)小問題，再各個(gè)擊破，在實(shí)際開發(fā)過程中，遞歸函數(shù)可以解決許多數(shù)學(xué)問題，如計(jì)算給定數(shù)字階乘、產(chǎn)生斐波系列等。

構(gòu)成遞歸需要具備以下條件：

一個(gè)問題可以被拆分成多個(gè)子問題；
拆分前的原問題與拆分后的子問題除了數(shù)據(jù)規(guī)模不同，但處理問題的思路是一樣的；
不能無限制的調(diào)用本身，子問題需要有退出遞歸狀態(tài)的條件。

注意：編寫遞歸函數(shù)時(shí)，一定要有終止條件，否則就會(huì)無限調(diào)用下去，直到內(nèi)存溢出。

下面通過幾個(gè)示例來演示一下遞歸函數(shù)的使用。

斐波那契數(shù)列

下面我們就以遞歸函數(shù)的經(jīng)典示例 —— 斐波那契數(shù)列為例，演示如何通過Go語言編寫的遞歸函數(shù)來打印斐波那契數(shù)列。

數(shù)列的形式如下所示：

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

使用Go語言遞歸函數(shù)實(shí)現(xiàn)斐波那契數(shù)列的具體代碼如下所示：

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
}

輸出結(jié)果為：

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

數(shù)字階乘

一個(gè)正整數(shù)的階乘（factorial）是所有小于及等于該數(shù)的正整數(shù)的積，并且 0 的階乘為 1，自然數(shù) n 的階乘寫作n!，“基斯頓·卡曼”在 1808 年發(fā)明了n!這個(gè)運(yùn)算符號(hào)。

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

使用遞歸函數(shù)計(jì)算給定數(shù)的階乘，示例代碼如下所示：

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 的階乘是 %d\n", i, Factorial(uint64(i)))
}

輸出結(jié)果為：

10 的階乘是 3628800

多個(gè)函數(shù)組成遞歸

Go語言中也可以使用相互調(diào)用的遞歸函數(shù)，多個(gè)函數(shù)之間相互調(diào)用形成閉環(huán)，因?yàn)镚o語言編譯器的特殊性，這些函數(shù)的聲明順序可以是任意的，下面這個(gè)簡單的例子展示了函數(shù) odd 和 even 之間的相互調(diào)用：

package main
import (
    "fmt"
)
func main() {
    fmt.Printf("%d is even: is %t\n", 16, even(16)) // 16 is even: is true
    fmt.Printf("%d is odd: is %t\n", 17, odd(17))
    // 17 is odd: is true
    fmt.Printf("%d is odd: is %t\n", 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
}

運(yùn)行效果如下所示：