Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

194
Visualizações
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 Respostas
Responde à pergunta

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 Relatório

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 Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda