Skip to content

Fibonacci 序列 Generator

中等 约 25 分钟

你将构建什么

Two 函数: `fibIterative(n)` using 循环 and `fibRecursive(n)` using recursion, 两者都 returning nth Fibonacci 数字.

学习目标

  • Implement iterative 解答 using 循环
  • Implement recursive 解答使用基础情况
  • Compare 性能的 iteration 对比 recursion
  • 理解 Fibonacci 序列模式

前置要求

  • 循环 (for or 虽然)
  • 函数 and 返回值
  • Recursion 概念 (基础情况 + recursive call)

步骤

  1. 1

    Implement iterative version

    Use 循环到 构建序列从 底部上. 开始使用 fib(0)=0 and fib(1)=1, 然后每个 subsequent 数字是 总和的 上一个 two.

    代码
    function fibIterative(n) {
      if (n <= 1) return n;
      let prev = 0, curr = 1;
      for (let i = 2; i <= n; i++) {
        const next = prev + curr;
        prev = curr;
        curr = next;
      }
      return curr;
    }

    预期结果

    fibIterative(10) 返回 55.

  2. 2

    Implement recursive version

    编写 recursive 函数哪里 fib(n) = fib(n-1) + fib(n-2), 使用基础情况 fib(0)=0 and fib(1)=1. 函数 calls 它自己使用 smaller 实参.

    代码
    function fibRecursive(n) {
      if (n <= 1) return n;
      return fibRecursive(n - 1) + fibRecursive(n - 2);
    }

    预期结果

    fibRecursive(10) 返回 55.

  3. 3

    Compare 两者都方法

    Call 两者都函数使用相同输入 and compare results. 注意那个 recursive version 是 much slower for 大 n due 到 repeated calculations.

    代码
    console.log(fibIterative(10));  // 55
    console.log(fibRecursive(10)); // 55
    console.log(fibIterative(30));  // 832040 (fast)
    // fibRecursive(30) would be very slow due to exponential calls

    预期结果

    两者都返回 55 for n=10; iterative 是瞬时 for n=30.

  4. 4

    Generate 序列数组

    编写 helper 那个返回首先 n Fibonacci 数字 as 数组, using iterative 方法 for efficiency.

    代码
    function fibSequence(n) {
      const seq = [0, 1];
      for (let i = 2; i < n; i++) {
        seq.push(seq[i-1] + seq[i-2]);
      }
      return seq.slice(0, n);
    }
    console.log(fibSequence(10));
    // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

    预期结果

    数组的 首先 10 Fibonacci 数字.

  5. 5

    添加输入验证

    在主逻辑入口处添加输入验证:检查输入是否为有效数字、是否在允许范围内,对非法输入给出清晰提示而非崩溃。这是健壮程序的第一道防线。

    代码
    function validateInput(value, min, max) {
      if (typeof value !== "number" || Number.isNaN(value)) {
        throw new Error(`Invalid input: ${value} is not a number`);
      }
      if (value < min || value > max) {
        throw new Error(`Input ${value} out of range [${min}, ${max}]`);
      }
      return value;
    }
    
    // Usage
    const input = validateInput(rawInput, 1, 100);

    预期结果

    非法输入(非数字或超出范围)会抛出清晰的错误信息,合法输入正常通过。

自己动手试试

你学到了什么

你 implemented 相同 algorithm two 方式 and discovered 那个 recursion 能是 elegant 但 exponentially slower 不使用 memoization — iteration 是经常更多 practical for sequential computation.

相关资源

相关课程

  • 循环

    iterative version uses for 循环.

  • Recursion

    recursive version demonstrates 基础情况 + recursive call.

相关练习

查阅不认识的术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

查看术语表

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回主题