Fibonacci 序列 Generator
你将构建什么
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
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
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
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
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
添加输入验证
在主逻辑入口处添加输入验证:检查输入是否为有效数字、是否在允许范围内,对非法输入给出清晰提示而非崩溃。这是健壮程序的第一道防线。
代码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);预期结果
非法输入(非数字或超出范围)会抛出清晰的错误信息,合法输入正常通过。
提示
使用 try/catch 包裹调用处,向用户展示友好的错误提示。
自己动手试试
function fibIterative(n) {
// TODO: loop-based Fibonacci
}
function fibRecursive(n) {
// TODO: recursive Fibonacci with base case
}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;
}
function fibRecursive(n) {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
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]你学到了什么
你 implemented 相同 algorithm two 方式 and discovered 那个 recursion 能是 elegant 但 exponentially slower 不使用 memoization — iteration 是经常更多 practical for sequential computation.
相关资源
相关课程
相关练习
- Predict Factorial 输出
练习 tracing recursive 函数.
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。