volvamos a las funciones y estudiémoslas más a fondo.

Nuestro primer tema será la recursividad.

si no eres nuevo en la programación, entonces probablemente te resulte familiar y podrías saltarte este capítulo.

la recursión es un patrón de programación que es útil en situaciones en las que una tarea puede dividirse naturalmente en varias tareas del mismo tipo, pero más simples. O cuando una tarea se puede simplificar en una acción fácil más una variante más simple de la misma tarea. O, como veremos pronto, para lidiar con ciertas 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 recursión.

dos formas de pensar

Para algo simple de empezar – vamos a escribir una función pow(x, n)que eleva xa una potencia natural de n. En otras palabras, se multiplica x por sí mismo n veces.

pow(2, 2) = 4pow(2, 3) = 8pow(2, 4) = 16

Hay dos maneras de implementarla.,

tenga en cuenta cómo la variante recursiva es fundamentalmente diferente.

Cuando pow(x, n) se llama, la ejecución se divide en dos ramas:

 if n==1 = x /pow(x, n) = \ else = x * pow(x, n - 1)

1. Si n == 1, todo es trivial. Se llama la base de recursión, porque inmediatamente produce el resultado obvio: pow(x, 1)es igual a x.
2. en caso Contrario, podemos representar pow(x, n) x * pow(x, n - 1)., En matemáticas, uno escribiría xn = x * xn-1. Esto se llama un paso recursivo: transformamos la tarea en un simple acción (multiplicación por x) y una simple llamada de la misma tarea (pow menor n). Los siguientes pasos lo simplifican cada vez más hasta que n alcance 1.

también podemos decir que powse llama recursivamente a sí mismo hasta n == 1.,

por ejemplo, Para calcular pow(2, 4) el recurrente variante realiza estos pasos:

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

Así, la recursividad se reduce a una función de llamada a uno más simple y, a continuación, a manera aún más sencilla, y así sucesivamente, hasta que el resultado es obvio.,

el número máximo de llamadas anidadas (incluida la primera) se denomina profundidad de recursión. En nuestro caso, será exactamente n.

la profundidad máxima de recursión está limitada por el motor JavaScript. Podemos confiar en que es 10000, algunos motores permiten más, pero 100000 es probablemente fuera de límite para la mayoría de ellos. Hay optimizaciones automáticas que ayudan a aliviar esto («optimizaciones llamadas tail»), pero todavía no son compatibles en todas partes y funcionan solo en casos simples.

que limita la aplicación de la recursividad, pero sigue siendo muy amplia., Hay muchas tareas donde la forma recursiva de pensar da un código más simple, más fácil de mantener.

el contexto de ejecución y la pila

ahora vamos a examinar cómo funcionan las llamadas recursivas. Para eso buscaremos bajo el capó de las 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: donde está el flujo de control Ahora, 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 a ella.

Cuando una función realiza una llamada anidada, ocurre lo siguiente:

• La función actual se detiene.
• el contexto de ejecución asociado a él se recuerda en una estructura de datos especial llamada pila de contexto de ejecución.,
• se ejecuta la llamada anidada.
• después de que termina, el contexto de ejecución antiguo 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).

pow (2, 3)

al comienzo de la llamada pow(2, 3) el contexto de ejecución almacenará las variables: x = 2, n = 3, el flujo de ejecución está en la línea 1 de la función.,

Podemos dibujarlo como:

• Context: { x: 2, n: 3, at line 1 } pow(2, 3)

ahí es cuando la función comienza a ejecutarse., La condición de n == 1 es falsy, por lo que el flujo continúa en la segunda rama de if:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}alert( pow(2, 3) );

Las variables son las mismas, pero los cambios en las líneas, por lo que el contexto es ahora:

• Contexto: { x: 2, n: 3, en la línea 5 } pow(2, 3)

Para calcular x * pow(x, n - 1), necesitamos hacer un subcall de pow con nuevos argumentos pow(2, 2).,

pow (2, 2)

para hacer 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 absolutamente no importa. El proceso es el mismo para todas las funciones:

1. el contexto actual es «recordado» en la parte superior de la pila.
2. se crea el nuevo contexto para la subcall.
3. cuando se termina la subcall – el contexto anterior se abre de la pila, y su ejecución continúa.,

Aquí está la pila de contexto cuando ingresamos la subcall pow(2, 2):

• Context: { x: 2, n: 2, at line 1 } pow(2, 2)
• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

el nuevo contexto de ejecución actual está en la parte superior (y negrita), y los contextos recordados anteriores están a continuación.

Cuando terminemos la subcall – es fácil reanudar el contexto anterior, porque mantiene ambas variables y el lugar exacto del código donde se detuvo.,

pow(2, 1)

El proceso se repite: un nuevo subcall se realiza en línea 5, ahora con argumentos x=2, n=1.,

se crea un nuevo contexto de ejecución, el anterior se coloca encima de la pila:

• Context: { x: 2, n: 1, at line 1 } pow(2, 1)
• Context: { x: 2, n: 2, at line 5 } pow(2, 2)
• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

hay 2 contextos antiguos ahora y 1 actualmente en ejecución para pow(2, 1).,

La salida

Durante la ejecución de pow(2, 1), a diferencia de antes, la condición de n == 1 es truthy, por lo que la primera rama de if obras:

function pow(x, n) { if (n == 1) { return x; } else { return x * pow(x, n - 1); }}

no Hay más llamadas anidadas, por lo que la función de los acabados, volviendo 2.

a medida que la función termina, 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:

• Context: { x: 2, n: 2, at line 5 } pow(2, 2)
• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

luego se restaura el contexto anterior:

• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Cuando termina, tenemos un resultado de pow(2, 3) = 8.

la profundidad de recursión en este caso fue: 3.

como podemos ver en las ilustraciones anteriores, la profundidad de recursión es igual al número máximo de contexto en la pila.

tenga en cuenta los requisitos de memoria. Los contextos toman memoria., En nuestro caso, elevar a la potencia den en realidad requiere la memoria para los contextosn, para todos los valores inferiores den.

Un bucle basado en el algoritmo es más la memoria de ahorro:

function pow(x, n) { let result = 1; for (let i = 0; i < n; i++) { result *= x; } return result;}

La iterativo pow utiliza un único contexto cambiante i y result en el proceso. Sus requisitos de memoria son pequeños, fijos y no dependen de n.,

cualquier recursión puede ser reescrita como un bucle. La variante del lazo se puede hacer generalmente más eficaz.

But pero a veces la reescritura no es trivial, especialmente cuando la función utiliza diferentes subcalls recursivas dependiendo de las condiciones y fusiona sus resultados o cuando la ramificación es más intrincada. Y la optimización puede ser innecesaria y totalmente no vale la pena los esfuerzos.

la recursión puede dar un código más corto, más fácil de entender y soportar. Las optimizaciones no son necesarias en todos los lugares, sobre todo necesitamos un buen código, por eso se utiliza.,

traversals recursivo

otra gran aplicación de la recursión es un traversal recursivo.

Imagine, tenemos una empresa. La estructura del personal se puede presentar como un objeto:

En otras palabras, una empresa tiene departamentos.

• Un departamento puede tener una matriz de personal. Por ejemplo, sales el departamento tiene 2 empleados: John y Alice.

• O un departamento se puede dividir en cátedras, como development tiene dos ramas: sites y internals. Cada uno de ellos tiene su propio personal.,

• también es posible que cuando un subdepartamento crece, se divida en subdepartamentos (o equipos).

  Por ejemplo, la etiqueta sites departamento en el futuro pueden ser divididos en equipos de siteA y siteB. Y ellos, potencialmente, pueden dividirse aún más. Eso no está en la foto, solo algo para tener en mente.

Ahora digamos que queremos una función para obtener 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 hacer un bucle for sobre company con subloop anidado sobre departamentos de 1er nivel. Pero entonces necesitamos más subloops anidados para iterar sobre el personal en los departamentos de Nivel 2 Como sites? y luego otro subloop dentro de los de los departamentos de Nivel 3 que podrían aparecer en el futuro? Si ponemos 3-4 subloops anidados en el código para atravesar un solo objeto, se vuelve bastante feo.

probemos la recursividad.,

como podemos ver, cuando nuestra función obtiene un departamento para sumar, hay dos casos posibles:

1. O bien es un departamento «simple» con una matriz de personas – entonces podemos sumar los salarios en un bucle simple.
2. O es un objeto conN subdepartments – entonces podemos hacer N llamadas recursivas para obtener la suma de cada uno de los subdeps y combinar los resultados.

el 1er caso es la base de la recursión, el caso trivial, cuando obtenemos una matriz.

el segundo caso cuando obtenemos un objeto es el paso recursivo., Una tarea compleja se divide en subtareas para departamentos más pequeños. A su vez, pueden dividirse de nuevo, pero tarde o temprano la división terminará en (1).

El algoritmo es probablemente aún más fácil leer el código:

El código es corto y fácil de entender (con suerte?). Ese es el poder de la recursión. También funciona para cualquier nivel de anidamiento de subdepartamentos.,

Aquí está el diagrama de llamadas:

tenga en cuenta que el código utiliza funciones inteligentes que hemos visto antes:

• Método arr.reduce explicó en el capítulo de la Matriz de métodos para obtener la suma de la matriz.
• Loop for(val of Object.values(obj))para iterar sobre los valores de los objetos: Object.values devuelve una matriz de ellos.,

estructuras recursivas

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 de una estructura de empresa anterior.

un departamento de la empresa es:

• o bien una matriz de personas.
• o un objeto con departamentos.

para 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.
• HTML-comentarios.,
• otras etiquetas HTML (que a su vez pueden contener piezas 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 enlazada» que podría ser una mejor alternativa para los arrays en algunos casos.

lista enlazada

Imagine, queremos almacenar una lista ordenada de objetos.

La elección natural sería una matriz:

let arr = ;

…Pero hay un problema con las matrices., Las operaciones» Eliminar elemento «e» insertar elemento » son costosas. Por ejemplo, arr.unshift(obj) la operación tiene que renumerar todos los elementos para hacer espacio para un nuevo obj, y si el array es grande, lleva tiempo. Lo mismo con arr.shift().

las únicas modificaciones estructurales que no requieren renumeración en masa son aquellas que operan con el final del array: arr.push/pop. Así que un array puede ser bastante lento para grandes colas, cuando tenemos que trabajar con 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 lista enlazado se define recursivamente como un objeto con:

• value.
• next propiedad que hace referencia al siguiente elemento de Lista vinculado o null si ese es el final.,

For instance:

let list = { value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: null } } }};

Graphical representation of the list:

An alternative code for creation:

let list = { value: 1 };list.next = { value: 2 };list.next.next = { value: 3 };list.next.next.next = { value: 4 };list.next.next.next.next = null;

Here we can even more clearly see that there are multiple objects, each one has the value and next pointing to the neighbour., La variable list es el primer objeto de la cadena, por lo que siguiendo los punteros next desde ella podemos llegar a cualquier elemento.

La lista puede ser fácilmente dividido en varias partes y más tarde se unió a la espalda:

let secondList = list.next.next;list.next.next = null;

Para unirse:

list.next.next = secondList;

Y sin duda podemos insertar o eliminar elementos en cualquier lugar.,head of the list:

To remove a value from the middle, change next of the previous one:

list.next = list.next.next;

We made list.next jump over 1 to value 2., El valor 1 ahora está excluido de la cadena. Si no se almacena en ningún otro lugar, se eliminará automáticamente de la memoria.

a diferencia de los arrays, no hay renumeración en masa, podemos reorganizar fácilmente los elementos.

naturalmente, las listas no siempre son mejores que los arrays. De lo contrario, todo el mundo usaría solo listas.

el principal inconveniente es que no podemos acceder fácilmente a un elemento por su número. En una matriz que es fácil: arr es una referencia directa., Pero en la lista necesitamos comenzar desde el primer elemento e ir next N times para obtener el enésimo elemento.

But pero no siempre necesitamos tales operaciones. Por ejemplo, cuando necesitamos una cola o incluso un deque, la estructura ordenada que debe permitir Agregar / Eliminar elementos muy rápidamente de 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 hace referencia al último elemento de la lista (y actualizarlo al Agregar/Eliminar elementos del final).
• The la estructura de datos puede variar según nuestras necesidades.

resumen

Términos:

• recursión es un término de programación que significa llamar a una función desde sí mismo. Las funciones recursivas se pueden utilizar para resolver tareas de manera elegante.

  Cuando una función se llama a sí misma, se llama un paso de recursión., La base de la recursión son argumentos de función que hacen que la tarea sea tan simple que la función no haga más llamadas.

• una estructura de datos definida recursivamente es una estructura de datos que se puede definir por sí misma.

  por ejemplo, la lista enlazada se puede definir como una estructura de datos que consiste en un objeto que hace referencia a una lista (o null).

  list = { value, next -> list }

  los Árboles como elementos HTML árbol o en el departamento de árbol de este capítulo son también, naturalmente, recursiva: que rama y cada sucursal puede tener otras ramas.,

  Las Funciones recursivas se pueden usar para recorrerlas como hemos visto en el ejemplo sumSalary.

cualquier función recursiva puede ser reescrita en una iterativa. Y eso a veces es necesario para optimizar las cosas. Pero para muchas tareas, una solución recursiva es lo suficientemente rápida y fácil de escribir y soportar.