Business
Jobs
  • About Us
  • Solutions
    • Job Postings
      Post your job and receive qualified candidates in 48h.
    • Candidate Assessments
      500+ technical and psychological tests, plus anti-fraud.
    • Headhunting
      Tailor-made executive search from start to finish.
    • Payroll + EOR
      Payroll dispersal and EOR across 15+ LATAM countries.
  • Pricing
  • Jobs

0

182
Views
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?

about 4 years ago · Juan Pablo Isaza
2 answers
Answer question

0

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);
}

about 4 years ago · Juan Pablo Isaza Report

0

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

about 4 years ago · Juan Pablo Isaza Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Sales
Legal
Terms and conditions Privacy policy
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Show me some job opportunities
There's an error!