go语言中实现斐波那契数列

Go  /  管理员 发布于 3年前   1075

基本上只要是语言就都有这东西，很经典，递归的经典使用题型

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”

1.写法一

按照表达式来实现

func fib(n int) int {
if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return fib(n-1)+fib(n-2)
}

2.写法二

func fib(n int) int {
    const mod int = 1e9 + 7
    if n < 2 {
        return n
    }
    p, q, r := 0, 0, 1
    for i := 2; i <= n; i++ {
        p = q
        q = r
        r = (p + q) % mod
    }
    return r
}

3.写法三

使用尾递归种优化

func fib(n int64) int64 {
    return getFibNum(0, 1, n)
}
func getFibNum(first, second, n int) int {
    const mod int = 1e9 + 7 // leetcode要求
    if n < 2 {
        return n
    }
    if 2 == n {
        return first + second
    }
    return getFibNum(second, first+second, n-1)%mod
}

leetcode：

https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/