Volvamos a las funciones y estudiémoslas más en profundidad.
Nuestro primer tema será la recursividad .
Si no es nuevo en la programación, probablemente le resulte familiar y podría saltarse este capítulo.
La recursividad es un patrón de programación que resulta útil en situaciones en las que una tarea se puede dividir de forma natural en varias tareas del mismo tipo, pero más sencillas. O cuando una tarea se puede simplificar en una acción sencilla más una variante más sencilla de la misma tarea. O, como veremos pronto, para tratar con determinadas estructuras de datos.
Cuando una función resuelve una tarea, en el proceso puede llamar a muchas otras funciones. Un caso parcial de esto es cuando una función se llama a sí misma . Eso se llama recursividad .
Para empezar con algo sencillo, escribamos una función pow(x, n) que eleve x a una potencia natural de n . En otras palabras, multiplica x por sí mismo n veces.
potencia(2, 2) = 4 potencia(2, 3) = 8 potencia(2, 4) = 16
Hay dos formas de implementarlo.
Pensamiento iterativo: el bucle for :
función poder(x, n) {
dejar resultado = 1;
// multiplica el resultado por x n veces en el bucle
para (sea i = 0; i < n; i++) {
resultado *= x;
}
resultado de devolución;
}
alerta( pow(2, 3) ); // 8Pensamiento recursivo: simplifica la tarea y llámate a ti mismo:
función poder(x, n) {
si (n == 1) {
devolver x;
} demás {
devolver x * pow(x, n - 1);
}
}
alerta( pow(2, 3) ); // 8Tenga en cuenta que la variante recursiva es fundamentalmente diferente.
Cuando se llama pow(x, n) , la ejecución se divide en dos ramas:
si n==1 = x
/
potencia(x, n) =
más = x * pow(x, n - 1) Si n == 1 , entonces todo es trivial. Se llama base de recursividad porque produce inmediatamente el resultado obvio: pow(x, 1) es igual a x .
De lo contrario, podemos representar pow(x, n) como x * pow(x, n - 1) . En matemáticas, se escribiría x n = x * x n-1 . A esto se le llama paso recursivo : transformamos la tarea en una acción más simple (multiplicación por x ) y una llamada más simple de la misma tarea ( pow con n menor). Los siguientes pasos lo simplifican cada vez más hasta que n llega a 1 .
También podemos decir que pow se llama a sí mismo recursivamente hasta n == 1 .
Por ejemplo, para calcular pow(2, 4) la variante recursiva sigue estos pasos:
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
Entonces, la recursividad reduce una llamada a una función a una más simple, y luego a una aún más simple, y así sucesivamente, hasta que el resultado se vuelve obvio.
La recursividad suele ser más corta.
Una solución recursiva suele ser más corta que una iterativa.
¿Aquí podemos reescribir lo mismo usando el operador condicional ? en lugar de if para hacer pow(x, n) más conciso y aún muy legible:
función poder(x, n) {
devolver (n == 1)? x : (x * pow(x, n - 1));
} El número máximo de llamadas anidadas (incluida la primera) se llama profundidad de recursividad . En nuestro caso, será exactamente n .
La profundidad máxima de recursividad está limitada por el motor JavaScript. Podemos confiar en que sea 10000, algunos motores permiten más, pero 100000 probablemente esté fuera del límite para la mayoría de ellos. Existen optimizaciones automáticas que ayudan a aliviar esto (“optimizaciones de llamadas finales”), pero aún no son compatibles en todas partes y solo funcionan en casos simples.
Eso limita la aplicación de la recursividad, pero sigue siendo muy amplia. Hay muchas tareas en las que la forma de pensar recursiva proporciona un código más simple y más fácil de mantener.
Ahora examinemos cómo funcionan las llamadas recursivas. Para eso veremos debajo del capó de funciones.
La información sobre el proceso de ejecución de una función en ejecución se almacena en su contexto de ejecución .
El contexto de ejecución es una estructura de datos interna que contiene detalles sobre la ejecución de una función: dónde está ahora el flujo de control, las variables actuales, el valor de this (no lo usamos aquí) y algunos otros detalles internos.
Una llamada a función tiene exactamente un contexto de ejecución asociado.
Cuando una función realiza una llamada anidada, sucede lo siguiente:
La función actual está en pausa.
El contexto de ejecución asociado con él se recuerda en una estructura de datos especial llamada pila de contexto de ejecución .
La llamada anidada se ejecuta.
Una vez finalizado, el contexto de ejecución anterior se recupera de la pila y la función externa se reanuda desde donde se detuvo.
Veamos qué sucede durante la llamada pow(2, 3) .
Al comienzo de la llamada pow(2, 3) el contexto de ejecución almacenará variables: x = 2, n = 3 , el flujo de ejecución está en la línea 1 de la función.
Podemos bosquejarlo como:
Contexto: { x: 2, n: 3, en la línea 1 } pow(2, 3)
Ahí es cuando la función comienza a ejecutarse. La condición n == 1 es falsa, por lo que el flujo continúa hacia la segunda rama de if :
función poder(x, n) {
si (n == 1) {
devolver x;
} demás {
devolver x * pow(x, n - 1);
}
}
alerta( pow(2, 3) );Las variables son las mismas, pero la línea cambia, por lo que el contexto ahora es:
Contexto: { x: 2, n: 3, en la línea 5 } pow(2, 3)
Para calcular x * pow(x, n - 1) , necesitamos hacer una subllamada de pow con nuevos argumentos pow(2, 2) .
Para realizar una llamada anidada, JavaScript recuerda el contexto de ejecución actual en la pila de contexto de ejecución .
Aquí llamamos a la misma función pow , pero no importa en absoluto. El proceso es el mismo para todas las funciones:
El contexto actual se "recuerda" en la parte superior de la pila.
Se crea el nuevo contexto para la subllamada.
Cuando finaliza la subllamada, el contexto anterior se extrae de la pila y su ejecución continúa.
Aquí está la pila de contexto cuando ingresamos la subllamada pow(2, 2) :
Contexto: { x: 2, n: 2, en la línea 1 } pow(2, 2)
Contexto: { x: 2, n: 3, en la línea 5 } pow(2, 3)
El nuevo contexto de ejecución actual está en la parte superior (y en negrita), y los contextos anteriores recordados están debajo.
Cuando terminamos la subllamada, es fácil reanudar el contexto anterior, porque mantiene ambas variables y el lugar exacto del código donde se detuvo.
Tenga en cuenta:
Aquí en la imagen usamos la palabra "línea", ya que en nuestro ejemplo solo hay una subllamada en línea, pero generalmente una sola línea de código puede contener múltiples subllamadas, como pow(…) + pow(…) + somethingElse(…) .
Por tanto, sería más preciso decir que la ejecución se reanuda “inmediatamente después de la subconvocatoria”.
El proceso se repite: se realiza una nueva subllamada en la línea 5 , ahora con argumentos x=2 , n=1 .
Se crea un nuevo contexto de ejecución y el anterior se coloca en la parte superior de la pila:
Contexto: { x: 2, n: 1, en la línea 1 } pow(2, 1)
Contexto: { x: 2, n: 2, en la línea 5 } pow(2, 2)
Contexto: { x: 2, n: 3, en la línea 5 } pow(2, 3)
Ahora hay 2 contextos antiguos y 1 actualmente ejecutándose para pow(2, 1) .
Durante la ejecución de pow(2, 1) , a diferencia de antes, la condición n == 1 es verdadera, por lo que la primera rama de if funciona:
función poder(x, n) {
si (n == 1) {
devolver x;
} demás {
devolver x * pow(x, n - 1);
}
} No hay más llamadas anidadas, por lo que la función finaliza y devuelve 2 .
Cuando la función finaliza, su contexto de ejecución ya no es necesario, por lo que se elimina de la memoria. El anterior se restaura desde la parte superior de la pila:
Contexto: { x: 2, n: 2, en la línea 5 } pow(2, 2)
Contexto: { x: 2, n: 3, en la línea 5 } pow(2, 3)
Se reanuda la ejecución de pow(2, 2) . Tiene el resultado de la subllamada pow(2, 1) , por lo que también puede finalizar la evaluación de x * pow(x, n - 1) , devolviendo 4 .
Luego se restablece el contexto anterior:
Contexto: { x: 2, n: 3, en la línea 5 } pow(2, 3)
Cuando termina, tenemos un resultado de pow(2, 3) = 8 .
La profundidad de recursividad en este caso fue: 3 .
Como podemos ver en las ilustraciones anteriores, la profundidad de recursividad es igual al número máximo de contexto en la pila.
Tenga en cuenta los requisitos de memoria. Los contextos requieren memoria. En nuestro caso, elevar a la potencia de n en realidad requiere memoria para n contextos, para todos los valores inferiores de n .
Un algoritmo basado en bucle ahorra más memoria:
función poder(x, n) {
dejar resultado = 1;
para (sea i = 0; i < n; i++) {
resultado *= x;
}
resultado de devolución;
} El pow iterativo utiliza un contexto único que cambia i y result en el proceso. Sus requisitos de memoria son pequeños, fijos y no dependen de n .
Cualquier recursividad se puede reescribir como un bucle. La variante en bucle normalmente puede hacerse más efectiva.
…Pero a veces la reescritura no es trivial, especialmente cuando una función usa diferentes subllamadas recursivas dependiendo de las condiciones y fusiona sus resultados o cuando la bifurcación es más compleja. Y la optimización puede ser innecesaria y no vale la pena el esfuerzo.
La recursividad puede proporcionar un código más corto, más fácil de entender y soportar. No se requieren optimizaciones en todos los lugares, principalmente necesitamos un buen código, por eso se usa.
Otra gran aplicación de la recursividad es el recorrido recursivo.
Imagínese, tenemos una empresa. La estructura del personal se puede presentar como un objeto:
dejar empresa = {
ventas: [{
nombre: 'Juan',
salario: 1000
}, {
nombre: 'Alicia',
salario: 1600
}],
desarrollo: {
sitios: [{
nombre: 'Pedro',
salario: 2000
}, {
nombre: 'Alex',
salario: 1800
}],
internos: [{
nombre: 'Jack',
salario: 1300
}]
}
};En otras palabras, una empresa tiene departamentos.
Un departamento puede tener una variedad de personal. Por ejemplo, el departamento sales tiene 2 empleados: John y Alice.
O un departamento puede dividirse en subdepartamentos, como si development tuviera dos ramas: sites e internals . Cada uno de ellos tiene su propio personal.
También es posible que cuando un subdepartamento crece, se divida en subsubdepartamentos (o equipos).
Por ejemplo, en el futuro el departamento sites puede dividirse en equipos para siteA y siteB . Y ellos, potencialmente, pueden dividirse aún más. Eso no está en la foto, sólo es algo a tener en cuenta.
Ahora digamos que queremos que una función obtenga la suma de todos los salarios. ¿Cómo podemos hacer eso?
Un enfoque iterativo no es fácil porque la estructura no es simple. La primera idea puede ser crear un bucle for sobre company con un subbucle anidado sobre los departamentos de primer nivel. Pero luego necesitamos más subbucles anidados para iterar sobre el personal en departamentos de segundo nivel, como sites ... ¿Y luego otro subbucle dentro de los de departamentos de tercer nivel que podría aparecer en el futuro? Si ponemos 3-4 subbucles anidados en el código para atravesar un solo objeto, se vuelve bastante feo.
Intentemos la recursividad.
Como podemos ver, cuando nuestra función consigue sumar un departamento, hay dos casos posibles:
O se trata de un departamento “simple” con una variedad de personas; entonces podemos sumar los salarios en un bucle simple.
O es un objeto con N subdepartamentos; entonces podemos realizar N llamadas recursivas para obtener la suma de cada uno de los subdepartamentos y combinar los resultados.
El primer caso es la base de la recursividad, el caso trivial, cuando obtenemos una matriz.
El segundo caso en el que obtenemos un objeto es el paso recursivo. Una tarea compleja se divide en subtareas para departamentos más pequeños. A su vez, pueden volver a dividirse, pero tarde o temprano la división terminará en (1).
El algoritmo probablemente sea incluso más fácil de leer en el código:
let company = { // el mismo objeto, comprimido por brevedad
ventas: [{nombre: 'John', salario: 1000}, {nombre: 'Alice', salario: 1600 }],
desarrollo: {
sitios: [{nombre: 'Peter', salario: 2000}, {nombre: 'Alex', salario: 1800 }],
internos: [{nombre: 'Jack', salario: 1300}]
}
};
// La función para hacer el trabajo.
función sumaSalarios(departamento) {
if (Array.isArray(departamento)) { // caso (1)
return departamento.reduce((anterior, actual) => anterior + actual.salario, 0); // suma la matriz
} más { // caso (2)
sea suma = 0;
for (dejemos subdep de Object.values(departamento)) {
suma += sumaSalarios(subdep); // llama recursivamente a subdepartamentos, suma los resultados
}
suma de devolución;
}
}
alert(sumaSalarios(empresa)); // 7700El código es breve y fácil de entender (¿con suerte?). Ese es el poder de la recursividad. También funciona para cualquier nivel de anidamiento de subdepartamentos.
Aquí está el diagrama de llamadas:
Podemos ver fácilmente el principio: para un objeto {...} se realizan subllamadas, mientras que los arrays [...] son las “hojas” del árbol de recursividad y dan un resultado inmediato.
Tenga en cuenta que el código utiliza funciones inteligentes que hemos cubierto antes:
Método arr.reduce explicado en el capítulo Métodos de matriz para obtener la suma de la matriz.
Bucle for(val of Object.values(obj)) para iterar sobre los valores del objeto: Object.values devuelve una matriz de ellos.
Una estructura de datos recursiva (definida recursivamente) es una estructura que se replica a sí misma en partes.
Lo acabamos de ver en el ejemplo anterior de la estructura de una empresa.
Un departamento de la empresa es:
O una variedad de personas.
O un objeto con departamentos .
Para los desarrolladores web hay ejemplos mucho más conocidos: documentos HTML y XML.
En el documento HTML, una etiqueta HTML puede contener una lista de:
Piezas de texto.
Comentarios HTML.
Otras etiquetas HTML (que a su vez pueden contener fragmentos de texto/comentarios u otras etiquetas, etc.).
Esa es una vez más una definición recursiva.
Para una mejor comprensión, cubriremos una estructura recursiva más llamada "Lista vinculada" que podría ser una mejor alternativa para las matrices en algunos casos.
Imagínese, queremos almacenar una lista ordenada de objetos.
La elección natural sería una matriz:
let arr = [obj1, obj2, obj3];
…Pero hay un problema con las matrices. Las operaciones de “eliminar elemento” e “insertar elemento” son costosas. Por ejemplo, la operación arr.unshift(obj) tiene que volver a numerar todos los elementos para dejar espacio para un nuevo obj , y si la matriz es grande, lleva tiempo. Lo mismo ocurre con arr.shift() .
Las únicas modificaciones estructurales que no requieren una nueva numeración masiva son aquellas que operan con el final de la matriz: arr.push/pop . Entonces, una matriz puede ser bastante lenta para colas grandes, cuando tenemos que trabajar desde el principio.
Alternativamente, si realmente necesitamos una inserción/eliminación rápida, podemos elegir otra estructura de datos llamada lista vinculada.
El elemento de la lista enlazada se define recursivamente como un objeto con:
value .
next propiedad que hace referencia al siguiente elemento de la lista vinculada o null si ese es el final.
Por ejemplo:
dejar lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
siguiente: nulo
}
}
}
};Representación gráfica de la lista:
Un código alternativo para la creación:
let lista = { valor: 1 };
lista.siguiente = { valor: 2 };
lista.siguiente.siguiente = { valor: 3 };
lista.siguiente.siguiente.siguiente = { valor: 4 };
lista.siguiente.siguiente.siguiente.siguiente = nulo; Aquí podemos ver aún más claramente que hay múltiples objetos, cada uno tiene el value y next apunta al vecino. La variable list es el primer objeto de la cadena, por lo que siguiendo next punteros podemos llegar a cualquier elemento.
La lista se puede dividir fácilmente en varias partes y luego volver a unirlas:
let segundaLista = lista.siguiente.siguiente; lista.siguiente.siguiente = nulo;
Para unirse:
lista.siguiente.siguiente = segundaLista;
Y seguramente podremos insertar o quitar elementos en cualquier lugar.
Por ejemplo, para anteponer un nuevo valor, necesitamos actualizar el encabezado de la lista:
let lista = { valor: 1 };
lista.siguiente = { valor: 2 };
lista.siguiente.siguiente = { valor: 3 };
lista.siguiente.siguiente.siguiente = { valor: 4 };
// antepone el nuevo valor a la lista
lista = { valor: "nuevo elemento", siguiente: lista }; Para eliminar un valor del medio, cambie next del anterior:
lista.siguiente = lista.siguiente.siguiente;
Hicimos que list.next saltara de 1 al valor 2 . El valor 1 ahora está excluido de la cadena. Si no está almacenado en ningún otro lugar, se eliminará automáticamente de la memoria.
A diferencia de las matrices, no hay una renumeración masiva, podemos reorganizar los elementos fácilmente.
Naturalmente, las listas no siempre son mejores que las matrices. De lo contrario, todos usarían sólo listas.
El principal inconveniente es que no podemos acceder fácilmente a un elemento por su número. En una matriz, eso es fácil: arr[n] es una referencia directa. Pero en la lista debemos comenzar desde el primer elemento y next N veces para obtener el enésimo elemento.
…Pero no siempre necesitamos este tipo de operaciones. Por ejemplo, cuando necesitamos una cola o incluso una deque, la estructura ordenada que debe permitir agregar/eliminar elementos muy rápidamente desde ambos extremos, pero no es necesario acceder a su centro.
Las listas se pueden mejorar:
Podemos agregar la propiedad prev además de next para hacer referencia al elemento anterior, para retroceder fácilmente.
También podemos agregar una variable llamada tail que haga referencia al último elemento de la lista (y actualizarla al agregar/eliminar elementos del final).
…La estructura de datos puede variar según nuestras necesidades.
Términos:
La recursividad es un término de programación que significa llamar a una función desde sí misma. Las funciones recursivas se pueden utilizar para resolver tareas de forma elegante.
Cuando una función se llama a sí misma, se denomina paso de recursividad . La base de la recursividad son los argumentos de la función que hacen que la tarea sea tan simple que la función no realiza más llamadas.
Una estructura de datos definida de forma recursiva es una estructura de datos que se puede definir utilizándose a sí misma.
Por ejemplo, la lista vinculada se puede definir como una estructura de datos que consta de un objeto que hace referencia a una lista (o nula).
lista = { valor, siguiente -> lista }Los árboles como el árbol de elementos HTML o el árbol de departamentos de este capítulo también son naturalmente recursivos: tienen ramas y cada rama puede tener otras ramas.
Se pueden usar funciones recursivas para recorrerlos, como hemos visto en el ejemplo sumSalary .
Cualquier función recursiva se puede reescribir en una iterativa. Y eso a veces es necesario para optimizar cosas. Pero para muchas tareas una solución recursiva es lo suficientemente rápida y más fácil de escribir y soportar.
importancia: 5
Escribe una función sumTo(n) que calcule la suma de los números 1 + 2 + ... + n .
Por ejemplo:
sumaA(1) = 1 sumaA(2) = 2 + 1 = 3 sumaA(3) = 3 + 2 + 1 = 6 sumaA(4) = 4 + 3 + 2 + 1 = 10 ... sumaA(100) = 100 + 99 + ... + 2 + 1 = 5050
Haga 3 variantes de solución:
Usando un bucle for.
Usando una recursividad, cause sumTo(n) = n + sumTo(n-1) para n > 1 .
Usando la fórmula de progresión aritmética.
Un ejemplo del resultado:
function sumTo(n) { /*... tu código... */ }
alerta( sumaA(100) ); // 5050PD: ¿Qué variante de solución es la más rápida? ¿El más lento? ¿Por qué?
PPS ¿Podemos usar la recursividad para contar sumTo(100000) ?
La solución usando un bucle:
función sumaA(n) {
sea suma = 0;
para (sea i = 1; i <= n; i++) {
suma += i;
}
suma de devolución;
}
alerta( sumaA(100) );La solución usando recursividad:
función sumaA(n) {
si (n == 1) devuelve 1;
devolver n + sumaA(n - 1);
}
alerta( sumaA(100) ); La solución usando la fórmula: sumTo(n) = n*(n+1)/2 :
función sumaA(n) {
devolver n * (n + 1) / 2;
}
alerta( sumaA(100) ); PD: Naturalmente, la fórmula es la solución más rápida. Utiliza solo 3 operaciones para cualquier número n . ¡Las matemáticas ayudan!
La variante loop es la segunda en términos de velocidad. Tanto en la variante recursiva como en la variante de bucle sumamos los mismos números. Pero la recursividad implica llamadas anidadas y gestión de la pila de ejecución. Eso también requiere recursos, por lo que es más lento.
PPS Algunos motores admiten la optimización de “llamada final”: si una llamada recursiva es la última en la función, sin realizar otros cálculos, entonces la función externa no necesitará reanudar la ejecución, por lo que el motor no necesita hacerlo. Recuerde su contexto de ejecución. Eso elimina la carga sobre la memoria. Pero si el motor JavaScript no admite la optimización de llamadas de cola (la mayoría de ellos no lo hacen), habrá un error: se excedió el tamaño máximo de pila, porque generalmente hay una limitación en el tamaño total de la pila.
importancia: 4
El factorial de un número natural es un número multiplicado por "number minus one" , luego por "number minus two" , y así sucesivamente hasta 1 . El factorial de n se denota como n!
Podemos escribir una definición de factorial así:
¡norte! = norte * (norte - 1) * (norte - 2) * ...*1
Valores de factoriales para diferentes n :
1! = 1 2! = 2 * 1 = 2 3! = 3 * 2 * 1 = 6 4! = 4 * 3 * 2 * 1 = 24 5! = 5 * 4 * 3 * 2 * 1 = 120
¡La tarea consiste en escribir una función factorial(n) que calcule n! usando llamadas recursivas.
alerta( factorial(5) ); // 120
PD: Pista: n! ¡Se puede escribir como n * (n-1)! Por ejemplo: 3! = 3*2! = 3*2*1! = 6
Por definición, un factorial n! ¡Se puede escribir como n * (n-1)! .
En otras palabras, el resultado de factorial(n) se puede calcular como n multiplicado por el resultado de factorial(n-1) . Y la llamada a n-1 puede descender recursivamente cada vez más hasta 1 .
función factorial(n) {
devolver (n! = 1)? norte * factorial(norte - 1) : 1;
}
alerta( factorial(5) ); // 120 La base de la recursividad es el valor 1 . También podemos hacer que 0 la base aquí, no importa mucho, pero da un paso recursivo más:
función factorial(n) {
volver n? norte * factorial(norte - 1) : 1;
}
alerta( factorial(5) ); // 120importancia: 5
La secuencia de números de Fibonacci tiene la fórmula F n = F n-1 + F n-2 . En otras palabras, el siguiente número es la suma de los dos anteriores.
Los primeros dos números son 1 , luego 2(1+1) , luego 3(1+2) , 5(2+3) y así sucesivamente: 1, 1, 2, 3, 5, 8, 13, 21... .
Los números de Fibonacci están relacionados con la proporción áurea y con muchos fenómenos naturales que nos rodean.
Escribe una función fib(n) que devuelva el n-th número de Fibonacci.
Un ejemplo de trabajo:
function fib(n) { /* tu código */ }
alerta(fib(3)); // 2
alerta(fib(7)); // 13
alerta(fib(77)); // 5527939700884757 PD: La función debería ser rápida. La llamada a fib(77) no debería tardar más de una fracción de segundo.
La primera solución que podríamos probar aquí es la recursiva.
Los números de Fibonacci son recursivos por definición:
función fib(n) {
devolver n <= 1? n : fib(n - 1) + fib(n - 2);
}
alerta (fib(3)); // 2
alerta (fib(7)); // 13
// fib(77); // ¡será extremadamente lento! …Pero para valores grandes de n es muy lento. Por ejemplo, fib(77) puede bloquear el motor durante algún tiempo y consumir todos los recursos de la CPU.
Esto se debe a que la función realiza demasiadas subllamadas. Los mismos valores se reevalúan una y otra vez.
Por ejemplo, veamos algunos cálculos para fib(5) :
... fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) ...
Aquí podemos ver que el valor de fib(3) es necesario tanto para fib(5) como para fib(4) . Entonces fib(3) será llamado y evaluado dos veces de forma completamente independiente.
Aquí está el árbol de recursividad completo:
Podemos notar claramente que fib(3) se evalúa dos veces y fib(2) se evalúa tres veces. La cantidad total de cálculos crece mucho más rápido que n , lo que la hace enorme incluso para n=77 .
Podemos optimizar eso recordando valores ya evaluados: si un valor de, digamos, fib(3) se calcula una vez, entonces podemos reutilizarlo en cálculos futuros.
Otra variante sería abandonar la recursividad y utilizar un algoritmo basado en bucles totalmente diferente.
En lugar de ir de n a valores más bajos, podemos hacer un bucle que comience desde 1 y 2 , luego obtenga fib(3) como su suma, luego fib(4) como la suma de dos valores anteriores, luego fib(5) y sube y sube, hasta llegar al valor necesario. En cada paso sólo necesitamos recordar dos valores anteriores.
Aquí se detallan los pasos del nuevo algoritmo.
El comienzo:
// a = fib(1), b = fib(2), estos valores son por definición 1 sea a = 1, b = 1; // obtenemos c = fib(3) como su suma sea c = a + b; /* ahora tenemos fib(1), fib(2), fib(3) a b c 1, 1, 2 */
Ahora queremos obtener fib(4) = fib(2) + fib(3) .
Cambiemos las variables: a,b obtendrá fib(2),fib(3) y c obtendrá su suma:
a = b; // ahora a = fib(2) segundo = c; // ahora b = fib(3) c = a + b; // c = fib(4) /* ahora tenemos la secuencia: a b c 1, 1, 2, 3 */
El siguiente paso da otro número de secuencia:
a = b; // ahora a = fib(3)
segundo = c; // ahora b = fib(4)
c = a + b; // c = fib(5)
/* ahora la secuencia es (un número más):
a b c
1, 1, 2, 3, 5
*/…Y así sucesivamente hasta obtener el valor necesario. Esto es mucho más rápido que la recursividad y no implica cálculos duplicados.
El código completo:
función fib(n) {
sea a = 1;
sea b = 1;
para (sea i = 3; i <= n; i++) {
sea c = a + b;
a = b;
segundo = c;
}
volver b;
}
alerta (fib(3)); // 2
alerta (fib(7)); // 13
alerta (fib(77)); // 5527939700884757 El ciclo comienza con i=3 , porque el primer y el segundo valor de secuencia están codificados en variables a=1 , b=1 .
El enfoque se llama programación dinámica ascendente.
importancia: 5
Digamos que tenemos una lista de enlace único (como se describe en el capítulo Recursión y pila):
dejar lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
siguiente: nulo
}
}
}
}; Escriba una función printList(list) que genere los elementos de la lista uno por uno.
Haga dos variantes de la solución: usando un bucle y usando recursividad.
¿Qué es mejor: con recursividad o sin ella?
La variante de la solución basada en bucles:
dejar lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
siguiente: nulo
}
}
}
};
función imprimirLista(lista) {
let tmp = lista;
mientras (tmp) {
alerta(tmp.valor);
tmp = tmp.siguiente;
}
}
imprimirLista(lista); Tenga en cuenta que utilizamos una variable temporal tmp para recorrer la lista. Técnicamente, podríamos usar una list de parámetros de función en su lugar:
función imprimirLista(lista) {
mientras (lista) {
alerta(lista.valor);
lista = lista.siguiente;
}
} …Pero eso sería imprudente. En el futuro, es posible que necesitemos ampliar una función o hacer algo más con la lista. Si cambiamos list , perdemos esa capacidad.
Hablando de buenos nombres de variables, list aquí es la lista misma. El primer elemento del mismo. Y así debería seguir siendo. Eso es claro y confiable.
Por otro lado, la función de tmp es exclusivamente un recorrido de lista, como i en el bucle for .
La variante recursiva de printList(list) sigue una lógica simple: para generar una lista debemos generar el elemento actual list y luego hacer lo mismo con list.next :
dejar lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
siguiente: nulo
}
}
}
};
función imprimirLista(lista) {
alerta(lista.valor); // genera el elemento actual
si (lista.siguiente) {
imprimirLista(lista.siguiente); //hace lo mismo con el resto de la lista
}
}
imprimirLista(lista);¿Ahora qué es mejor?
Técnicamente, el bucle es más eficaz. Estas dos variantes hacen lo mismo, pero el bucle no gasta recursos en llamadas a funciones anidadas.
Por otro lado, la variante recursiva es más corta y, a veces, más fácil de entender.
importancia: 5
Genere una lista de un solo enlace de la tarea anterior. Genere una lista de un solo enlace en el orden inverso.
Haga dos soluciones: usar un bucle y usar una recursividad.
La lógica recursiva es un poco complicada aquí.
Primero debemos generar el resto de la lista y luego generar la actual:
dejar lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
siguiente: nulo
}
}
}
};
función imprimirListaReversa(lista) {
si (lista.siguiente) {
printReverseList(lista.siguiente);
}
alerta(lista.valor);
}
printReverseList(lista);
La variante de bucle también es un poco más complicada que la salida directa.
No hay forma de obtener el último valor de nuestra list . Tampoco podemos “regresar”.
Entonces, lo que podemos hacer es primero revisar los elementos en orden directo y recordarlos en una matriz, y luego generar lo que recordamos en orden inverso:
dejar lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
siguiente: nulo
}
}
}
};
función imprimirListaReversa(lista) {
let arr = [];
let tmp = lista;
mientras (tmp) {
arr.push(tmp.valor);
tmp = tmp.siguiente;
}
for (sea i = longitud de arreglo - 1; i >= 0; i--) {
alerta( llegada[i] );
}
}
printReverseList(lista);Tenga en cuenta que la solución recursiva en realidad hace exactamente lo mismo: sigue la lista, recuerda los elementos en la cadena de llamadas anidadas (en la pila de contexto de ejecución) y luego los genera.