IMMUTABLE?

Performance Folks,

I just had an article[1] published in which I demonstrated recursive
PL/pgSQL functions with this function:

CREATE OR REPLACE FUNCTION fib (
fib_for int
) RETURNS integer AS $$
BEGIN
IF fib_for < 2 THEN
RETURN fib_for;
END IF;
RETURN fib(fib_for - 2) + fib(fib_for - 1);
END;
$$ LANGUAGE plpgsql;

Naturally, it's slow:

try=# \timing
try=# select fib(28);
fib
--------
317811
(1 row)

Time: 10642.803 ms

Now, I mistakenly said in my article that PostgreSQL doesn't have
native memoization, and so demonstrated how to use a table for
caching to speed up the function. It's pretty fast:

try=# select fib_cached(28);
fib_cached
------------
317811
(1 row)

Time: 193.316 ms

But over the weekend, I was looking at the Pg docs and saw IMMUTABLE,
and said, "Oh yeah!". So I recreated the function with IMMUTABLE. But
the performance was not much better:

try=# select fib(28);
fib
--------
317811
(1 row)

Time: 8505.668 ms
try=# select fib_cached(28);
fib_cached
------------
317811
(1 row)

So, what gives? Am I missing something, or not understanding how
IMMUTABLE works?

Many TIA,

David

1. http://www.onlamp.com/pub/a/onlamp/2006/05/11/postgresql-plpgsql.html