recursión de cola y de Fibonacci

Question

yo estaba buscando en este sitio: http://rosettacode.org/wiki/Fibonacci_sequence#JavaScript y vieron este programa:

function fib(n) { 
    return function(n,a,b) { 
    return n>0 ? arguments.callee(n-1,b,a+b) : a; 
    }(n,0,1); 
} 

¿Cómo funciona esto, ¿cuáles son esos dos argumentos (ayb) ayuda. Lo rastreé y todavía no puedo entender cómo funciona esto

Answer 1

En el function(n,a,b), n sirve como un contador de cuenta atrás, y ab almacena dos números de Fibonacci consecutivos para el propósito de calcular la siguiente, por lo que cuando n llega a 0, tiene a como el n + 1-ésimo número de Fibonacci (ya que el verdadero Fibonacci tiene dos 1s como el comienzo).

por ejemplo, n = 4:

n a b 
4 0 1 
3 1 2 
2 2 3 
1 3 5 
0 5 8 

Como se puede ver, el valor de A y B siempre igual a los números de Fibonacci. Además, este es muy similar a la programación funcional (como la página web decía Esquema programadores).

Answer 2

a y b son parámetros en una función anónima recién definida.

Me gustaría echar un vistazo a este page que es la documentación sobre el objeto arguments. De la documentación, arguments.callee, es una referencia a la función en la que se encuentra actualmente. Esto tiene que hacerse porque están trabajando en una función anónima, por lo que realmente no tiene nombre (que ellos conozcan).

Parece que llaman recursivamente a la función que definen (anónimamente) a una profundidad de n. A lo largo del camino, se están calculando los números fib y devuelven el valor a una vez que se ha alcanzado una profundidad de n. Los valores iniciales pasados ​​a la función son (n,0,1)

Answer 3

Como se explica here, arguments.callee se refiere a la función actual que se encuentra. Dado que la función se encuentra en el anonimato es , esta es la única manera de llamar a la función y lograr la recursividad.

La función específica calcula la Fibonacci sequence, llamando de forma recursiva en la función interna.

Answer 4

a y b representan el número actual de la secuencia y el siguiente número de la secuencia, a partir de 0 y 1. n es un temporizador de cuenta atrás que especifica qué elemento de la secuencia de Fibonacci será devuelto (EG: n = 10 volverá 55).

Esta función funciona mediante la aceptación de un argumento n lo que significa que calcular el número n de la secuencia:

function fib(n) { 

continuación, el código define una función que calcula el siguiente número de la secuencia:

function(n,a,b) { 
    return n>0 ? arguments.callee(n-1,b,a+b) : a; 
} 

Básicamente esta función anónima cuenta atrás n por uno cada vez que se está ejecutando, mientras que al mismo tiempo mueve a y b a los siguientes números en t la secuencia. Si n es igual a 0, entonces la secuencia se completa y se devuelve el número actual a.

arguments.callee se refiere a la función que se está ejecutando actualmente, por lo que el código solo significa volver a llamar a sí mismo con los nuevos argumentos. En otras palabras, para comenzar la próxima iteración del "bucle".

Finalmente, al decir (n,0,1); el código está llamando al fib con los parámetros n,0,1. La instrucción return, que dejé fuera del fragmento anterior, toma el valor de retorno de la función anónima y la devuelve a la persona que llama de fib.

---

Dicho esto, el uso de la repetición de esta manera es ineficiente para lenguajes como JavaScript que no tienen la optimización de llamada de cola. Para grandes n sería mejor escribir esto usando una construcción de bucle estándar en lugar de recursión.

Answer 5

Veo algunos problemas que pueden causar confusión. Breve optimización de la mano y la cola para el patrón de función recursiva.

El problema podría estar en la versión abreviada del código. Reescrito para mayor claridad a continuación.

1. reconociendo la función anónima, dándole un nombre "vuelva a ocurrir"
2. condicional (ternario) se expandió.

Tail Optimization se utiliza para domesticar el uso de la pila de funciones recursivas mediante la adición de una parte del acumulador. Este es un patrón común pero elimina la legibilidad. Esa es la función de recur.

Una nota especial que el rendimiento es excelente en comparación con iterar en un bucle.

function fib(n) { 
 
    function recur(n, a, b) { 
 
     if (n > 0) { 
 
      return recur(n - 1, b, a + b); 
 
     } else { 
 
      return a; 
 
     } 
 
    } 
 
    return recur(n, 0, 1); 
 
}

Con respecto a los parámetros, n es el contador de iteración, un y b son las partes de secuencia de Fibonacci.