The Pragmatic Programmer

Why This Fibonacci Code Is Smarter Than It Looks

Written by

fire_horse

in

At first glance, a Fibonacci function seems like a simple coding exercise. You take a number n, and return the nth number in the Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21…

Each number is the sum of the two before it.

Many beginners write Fibonacci using recursion because it feels natural. But while recursive code looks elegant, it can hide a major performance problem.

The Classic Recursive Version

var yourself = {
    fibonacci : function(n) {
        if (n === 0) {
            return 0;
        } else if (n === 1) {
            return 1;
        } else {
            return this.fibonacci(n - 1) +
                this.fibonacci(n - 2);
        }
    }
};

This works correctly, but it becomes painfully slow as n grows.

Why?

Because the function keeps solving the same subproblems repeatedly.

For example, to calculate fibonacci(6), it must calculate:

  • fibonacci(5)
  • fibonacci(4)

But inside fibonacci(5), it calculates fibonacci(4) again.

Then deeper down, it recalculates fibonacci(3), fibonacci(2), and so on many times.

The result is a lot of wasted work.

A Better Approach: Memoization

Memoization is a technique where you store previously calculated results so they can be reused instantly.

Instead of recalculating fibonacci(4) ten times, compute it once and save it.

Here’s the improved version:

var yourself = {
    cache: {},

    fibonacci: function(n) {
        if (n === 0) return 0;
        if (n === 1) return 1;

        if (this.cache[n] !== undefined) {
            return this.cache[n];
        }

        this.cache[n] =
            this.fibonacci(n - 1) +
            this.fibonacci(n - 2);

        return this.cache[n];
    }
};

What This Code Is Doing

The object contains two parts:

1. A cache

cache: {}

This stores answers that were already computed.

Example after running:

{
  2: 1,
  3: 2,
  4: 3,
  5: 5
}

2. A Fibonacci function

When asked for a value:

  • If it’s 0 or 1, return immediately.
  • If it already exists in the cache, use the saved answer.
  • Otherwise, calculate it, store it, and return it.

Why It’s Faster

The recursive version can explode into thousands or millions of repeated calls.

The memoized version calculates each Fibonacci number once.

That turns a slow problem into a fast one.

Real Lesson Behind This Example

This is not really about Fibonacci.

It teaches an important programming principle:

If a problem repeats the same work, store results and reuse them.

This idea appears everywhere:

  • Dynamic programming
  • Web caching
  • Database query optimization
  • API response caching
  • Machine learning pipelines

Final Thought

Sometimes the smartest code is not code that does more work. It is code that avoids doing the same work twice.

That small cache: {} line transforms a beginner exercise into a lesson in efficient thinking.

More posts