斐波那契數

題目描述：斐波那契數，通常用 F(n) 表示，形成的序列稱為 斐波那契數列 。該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和。也就是：

• F(0) = 0，F(1) = 1

• F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給你 n ，請計算 F(n) 。

示例說明請見LeetCode官網。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/fibonacci-number/ ??

著作權歸領扣網絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

解法一：遞歸法

當n小于2時，直接返回n，當n大于2時，通過公式F(n) = F(n - 1) + F(n - 2)遞歸調用當前方法并返回。

解法二：迭代法

當n小于2時，直接返回你，當n大于2時，通過迭代的方式計算當前值，具體過程如下：

• 記錄當前的值的前2位的值是lastSecond，記錄當前的值的前1位的值是lastOne；

• 然后從2開始遍歷，一直到n；

• 具體過程是將lastOne更新為lastSecond + lastOne，lastSecond更新為 之前的值；

最后返回lastOne的值即為當前值。

【每日寄語】 把機遇留給朋友，把幸運留給親人，把勤奮留給自己。