Fibonacci - Plain Recursion vs. Closure Caches (v3)

Revision 3 of this benchmark created on

Description

This test demonstrates the expressive power of closures. It is not written for pure performance comparison! In fact, caching the results when computing even larger fibonacci numbers, will be zillion times faster.

Caching of intermediate results could be achieved through other means, e.g. polluting the global namespace with an array, that your function uses for caching. But closures are an elegant way to tie some internal state to a function, that resides over all invocations.

Preparation HTML

<script>
  var fib_plain = function (n) {
          return (n <= 1) ? n :
                 fib_plain(n - 2) + fib_plain(n - 1);
      },
      fib_closure = function () {
          var cache = [];
          return function (n) {
              return (cache[n]) ? cache[n] :
                     (n <= 1) ? n :
                     (cache[n] = arguments.callee(n - 2) + arguments.callee(n - 1))
          };
      },
      fib_closure_2 = function () {
          var cache = [];
          var f = function (n) {
              return (cache[n]) ? cache[n] :
                     (n <= 1) ? n :
                     (cache[n] = f(n - 2) + f(n - 1))
          };
          return f;
      },
      fib_closure_3 = function () {
          var cache = [0, 1];
          var exist;
          var f = function (n) {
              if ((exist = cache[n]) != undefined) {
                  return exist;
              }
              return (cache[n] = f(n - 2) + f(n - 1))
          };
          return f;
      },
      fib_closure_4 = function () {
          var cache = [0, 1];
          var l = 1;
          var f = function (n) {
              if (n <= l) {
                  return cache[n];
              }
              for (l; l <= n; l++) {
                  cache[l] = cache[l-1] + cache[l-2]
              }
              return cache[n];
          };
          return f;
      };
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
Plain Recursion
fib_plain(0x23);
ready
Closure Caching
// we need to create a new closure everytime
fib_closure()(0x23);
ready
Closure Caching 2
// we need to create a new closure everytime
fib_closure_2()(0x23);
ready
Closure Caching 3
// we need to create a new closure everytime
fib_closure_3()(0x23);
ready
Closure Caching 4
// we need to create a new closure everytime
fib_closure_4()(0x23);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.