0

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?

J0hannes
  • 593
  • 5
  • 10
  • Does this answer your question? [Generating Fibonacci Sequence](https://stackoverflow.com/questions/7944239/generating-fibonacci-sequence) – Yogi Apr 17 '22 at 10:03

2 Answers2

3

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);
}
trincot
  • 317,000
  • 35
  • 244
  • 286
  • Aren't you missing memoization stuff? – Yevhen Horbunkov Apr 17 '22 at 10:06
  • Memoization is not relevant with this approach. – trincot Apr 17 '22 at 10:07
  • Yet it was mentioned a couple of times by OP, so it may be the essential part of the solution they're looking for. Isn't that reasonable from performance standpoint? – Yevhen Horbunkov Apr 17 '22 at 10:12
  • It is not reasonable from performance standpoint, since the generator produces the values from first to the next, etc, for which it is only necessary to maintain two consecutive Fibonacci numbers (the two parameters can be seen as temporary memoization if you wish). The algorithm where memoization would be used in a top down recursion, is used for when you need a *specific* Fibonacci number. But in the context of a generator, this is not useful. – trincot Apr 17 '22 at 10:29
  • Thank you trincot. Maybe you want to have a look at the attempt I made, before I posted this question? -> https://onecompiler.com/javascript/3xze3g7w2 why is it returning NaN after the first two values? And why is it returning in the fib sequence (in between NaNs) when I replace line 3 with: `if (values[x]) {`? – J0hannes Apr 17 '22 at 17:03
  • 1
    Sorry, I missed your comment. But there are many things wrong with that attempt. `yield*` returns undefined when you don't (always) return a value. Then `last + lastBefore` will give `NaN`. It is counter intuitive to use a generator like that. A generator is supposed to yield a series, so you should *consume* that iterator, also when calling it recursively. This is a pattern that in my opinion should not be used together with memoizaion in `values`. It is like you try to solve a problem with two distinct strategies at the same time. – trincot Apr 23 '22 at 09:47
2

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
pilchard
  • 12,414
  • 5
  • 11
  • 23