Skip to content

Fibonacci Sequence Generator

Medium ~25 min

What you'll build

Two functions: `fibIterative(n)` using a loop and `fibRecursive(n)` using recursion, both returning the nth Fibonacci number.

Goals

  • Implement an iterative solution using a loop
  • Implement a recursive solution with a base case
  • Compare performance of iteration vs recursion
  • Understand the Fibonacci sequence pattern

Prerequisites

  • Loops (for or while)
  • Functions and return values
  • Recursion concept (base case + recursive call)

Steps

  1. 1

    Implement the iterative version

    Use a loop to build the sequence from the bottom up. Start with fib(0)=0 and fib(1)=1, then each subsequent number is the sum of the previous two.

    Code
    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;
    }

    Expected result

    fibIterative(10) returns 55.

  2. 2

    Implement the recursive version

    Write a recursive function where fib(n) = fib(n-1) + fib(n-2), with base cases fib(0)=0 and fib(1)=1. The function calls itself with smaller arguments.

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

    Expected result

    fibRecursive(10) returns 55.

  3. 3

    Compare both approaches

    Call both functions with the same input and compare the results. Note that the recursive version is much slower for large n due to repeated calculations.

    Code
    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

    Expected result

    Both return 55 for n=10; iterative is instant for n=30.

  4. 4

    Generate a sequence array

    Write a helper that returns the first n Fibonacci numbers as an array, using the iterative approach for efficiency.

    Code
    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]

    Expected result

    An array of the first 10 Fibonacci numbers.

  5. 5

    Add input validation

    At the entry of the main logic, add input validation: check that the input is a valid number and within the allowed range, and show a clear message for invalid input instead of crashing. This is the first line of defense for a robust program.

    Code
    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);

    Expected result

    Invalid input (non-number or out of range) throws a clear error message; valid input passes through normally.

Try it yourself

What you learned

You implemented the same algorithm two ways and discovered that recursion can be elegant but exponentially slower without memoization — iteration is often more practical for sequential computation.

Related Resources

Related Lessons

  • Loops

    The iterative version uses a for loop.

  • Recursion

    The recursive version demonstrates base case + recursive call.

Related Practice

Look up unfamiliar terms

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

View glossary

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors

← Back to topic