简单
技术面试0 次浏览请实现一个函数,计算斐波那契数列的第 n 项。
算法工程师
递归斐波那契数列
答题要点
斐波那契数列是指这样一个数列:0、1、1、2、3、5、8、13、21、34、…… ,在数学上,斐波那契数列以如下递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)。可以使用递归或迭代的方法来实现计算斐波那契数列的第 n 项。递归方法的代码简洁,但效率较低,因为会有大量的重复计算。迭代方法则通过保存前两项的值,不断更新来计算下一项,效率较高。以下是迭代方法的实现:首先,若 n 为 0 则返回 0,若 n 为 1 则返回 1。然后初始化两个变量 a 和 b 分别为 0 和 1,通过循环从 2 到 n 进行迭代,每次更新 a 和 b 的值,最后返回 b。这种方法的时间复杂度为 O(n),空间复杂度为 O(1)。