CODEWITHSUNDEEP
javascriptgeneratorfibonaccimemoization
J0hannes
J0hannes

Reputation: 633

Can you do a recursive, memoized Fibonacci function using a js generator?

The most elegant Fibonacci function I have found isn't even recursive:

async function* fib(x) {
  let x1 = 0;
  let x2 = 1;
  let i = 0;
  while (i < x) {
    [x1, x2] = [x2, x1 + x2];
    i += 1;
  }
  yield x1;
}

Generators are great. That being said - they also lend themselves to recursive tasks, since you can execute them 'lazily'.

And traditionally, Fibonacci functions are textbook examples for recursion or memoization.

What I came up with so far doesn't work.

So I was wondering: How would you do a recursive, memoized Fibonacci generator function in JavaScript?

Upvotes: 0

Views: 632

Answers (2)

pilchard
pilchard

Reputation: 12919

Trincot's answer covers well the recursive generator aspect of you question and I agree with their assessment re: memoization in that case. Since it looks like you're looking to return a specific Fibonacci number you can simply memoize the function you posted in your question (minus async as it's not needed here). Keep in mind that since it only ever yields once, it could just as easily be a standard function since the cost will be paid regardless as soon as you access the next() (and only) element.

function memoFib() {
  const c = new Map();
  let m = 0;
  let x1 = 0;
  let x2 = 1;

  return function* (x) {
    while (m <= x) {
      c.set(m, x1);
      [x1, x2] = [x2, x1 + x2];
      m++;
    }

    yield c.get(x)
  }
}

const fib = memoFib();

console.log(fib(10).next().value); // updates cache
console.log(fib(2).next().value);
console.log(fib(5).next().value);
console.log(fib(14).next().value); // updates cache
console.log(fib(11).next().value);
console.log(fib(1).next().value);

It's a small next step to expand the above with Trincot's recursive example into a memoized function which returns specific ranges of the series as an iterator. The below snippet uses an array as a cache instead of a Map and accepts start and end indexes, if end is omitted it will return a sequence of 1. This makes better use of the generator and since the cache was already being populated sequentially an array is a better fit than a Map anyway.

function memoFib() {
  const c = [];
  let m = 0;
  let x1 = 0;
  let x2 = 1;

  return function* fib(start, end) {
    end = end ?? start + 1;

    while (m <= start) {
      c[m] = x1;
      [x1, x2] = [x2, x1 + x2];
      m++;
    }

    if (start < end) {
      yield c[start]
      yield* fib(start + 1, end)
    }
  }
}

const fib = memoFib();

console.log('Sequence:')
for (const n of fib(0, 5)) {
  console.log(n)
}

console.log('\nSingle values:')
console.log(fib(2).next().value);
console.log(fib(11).next().value); // updates cache
console.log(fib(10).next().value);
console.log(fib(14).next().value); // updates cache

Upvotes: 2

trincot
trincot

Reputation: 350310

Some preliminary comments:

  • async has nothing to do with yield. So remove async here.
  • For a generator it should be unnecessary to pass an argument that indicates the end of the series (x). This should be a limit that the caller imposes and the generator should not have to worry about. From the viewpoint of the generator, it should just keep going without limit for as long as the caller pulls values from it.
  • A recursive version would anyhow have to yield the first Fibonacci value before the others, so it would then make sense to apply a pattern that looks like tail recursion. This requires no memoization (except for passing on two consecutive Fibonacci values):

function* genFib (a=0, b=1) {
    yield a;
    yield *genFib(b, a+b);
}

let limit = 50;
for (let n of genFib()) {
    if (n > limit) break;
    console.log(n);
}

Upvotes: 3

Related Questions