La función de Fibonacci más elegante que he encontrado ni siquiera es recursiva:
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; }Los generadores son geniales. Dicho esto, también se prestan a tareas recursivas, ya que puede ejecutarlas 'perezosamente'.
Y tradicionalmente, las funciones de Fibonacci son ejemplos de libros de texto para recursividad o memorización.
Lo que se me ocurrió hasta ahora no funciona.
Así que me preguntaba: ¿Cómo haría una función de generador de Fibonacci memorizada y recursiva en JavaScript?
Algunos comentarios preliminares:
async no tiene nada que ver con el yield . Así que elimine async aquí.x ). Este debería ser un límite que impone la persona que llama y el generador no debería tener que preocuparse. Desde el punto de vista del generador, debería seguir funcionando sin límite mientras la persona que llama obtenga valores de él. 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); }La respuesta de Trincot cubre bien el aspecto del generador recursivo de su pregunta y estoy de acuerdo con su evaluación re: memorización en ese caso. Como parece que está buscando devolver un número de Fibonacci específico, simplemente puede memorizar la función que publicó en su pregunta (menos asíncrono, ya que no es necesario aquí). Tenga en cuenta que, dado que solo produce una vez, podría ser fácilmente una función estándar, ya que el costo se pagará tan pronto como acceda al elemento next() (y único).
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); Es un pequeño paso siguiente expandir lo anterior con el ejemplo recursivo de Trincot en una función memorizada que devuelve rangos específicos de la serie como un iterador. El siguiente fragmento utiliza una matriz como caché en lugar de un mapa y acepta índices de start y end ; si se omite el end , devolverá una secuencia de 1. Esto hace un mejor uso del generador y, dado que la memoria caché ya se estaba llenando secuencialmente, una matriz es un mejor ajuste que un Mapa de todos modos.
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