题目描述

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从0开始，第0项为0。(n<=39)

样例

输入整数 n=5 

返回 5

算法1

(暴力枚举)

正着枚举，非常简单。

时间复杂度

参考文献

Go 代码

func Fibonacci(n int) int {
    a,b:=0,1
    for i:=0;i<n;i++{
        a,b=b,a+b
    }
    return a
}

算法2

(递归)

通过递归，求得答案。

时间复杂度

参考文献

Go 代码

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