面试高频手撕题 | 06.计算斐波那契数列的第 n 个数

一、知识点

斐波那契数列（Fibonacci sequence），又称黄金分割数列，是一个经典的数学数列，起始于 0 和 1，后续的每一项都是前两项的和。其前几项如下：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

二、思路分析

计算斐波那契数列的第 n 个数，可以使用递归或迭代的方式。下面分别介绍这两种方法的思路：

1. 递归：

   • 定义一个递归函数，接受 n 作为参数。
   • 如果 n 等于 0 或 1，直接返回 n。
   • 否则，返回前两项的和，即 fib(n - 1) + fib(n - 2)。

2. 迭代：

   • 定义一个变量保存前两项的和。
   • 使用循环计算出前 n 项的和，最后一项即为第 n 个数。

三、JavaScript 解答

使用递归方式计算斐波那契数列的第 n 个数：

function fib(n) {
  if (n === 0 || n === 1) {
    return n;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
}

使用迭代方式计算斐波那契数列的第 n 个数：

function fibIterator(n) {
  let fibSeries = [0, 1];
  for (let i = 2; i <= n; i++) {
    fibSeries.push(fibSeries[i - 1] + fibSeries[i - 2]);
  }
  return fibSeries[n];
}

四、Java 解答

使用递