Voy a decir esto desde el principio. ¿Conoce los eventos que ocurren al invocar una función? ¿No? Entonces ahí es donde comenzaremos.
Invocación de función
Cuando llamamos a una función, se coloca un contexto de ejecución en la pila de ejecución. Analicemos esto un poco más.
Primero, ¿qué es una pila?
Una pila es una estructura de datos que opera sobre una base de "último en entrar, primero en salir". Un elemento se "empuja" a una pila para agregarlo, y un elemento se "saca" de la pila para eliminarlo.
Usar una pila es un método para ordenar ciertas operaciones para su ejecución.
Ahora, volvamos a lo que es un contexto de ejecución. Se forma un contexto de ejecución sobre la invocación de una función. Este contexto se coloca en una pila de ejecución, un orden de operaciones. El elemento que siempre está primero en esta pila es el contexto de ejecución global. El siguiente es cualquier contexto creado por función.
Estos contextos de ejecución tienen propiedades, un objeto de activación y un enlace "this". El enlace "this" es una referencia a este contexto de ejecución. El objeto de activación incluye: parámetros pasados, variables declaradas y declaraciones de funciones.
Entonces, cada vez que colocamos un nuevo contexto en la pila, generalmente tenemos todo lo que necesitamos para ejecutar el código.
¿Por qué digo habitualmente ?
Con la recursividad, estamos esperando valores de retorno provenientes de otros contextos de ejecución. Estos otros contextos están más arriba en la pila. Cuando el último elemento de la pila finaliza la ejecución, ese contexto genera un valor de retorno. Este valor de retorno se transmite como un valor de retorno del caso recursivo al siguiente elemento. Ese contexto de ejecución luego se extrae de la pila.
Recursividad
Entonces, ¿qué es la recursividad?
Una función recursiva es una función que se llama a sí misma hasta que una "condición base" es verdadera y la ejecución se detiene.
Si bien es falso, seguiremos colocando contextos de ejecución en la parte superior de la pila. Esto puede suceder hasta que tengamos un "desbordamiento de pila". Un desbordamiento de pila es cuando nos quedamos sin memoria para guardar elementos en la pila.
En general, una función recursiva tiene al menos dos partes: una condición base y al menos un caso recursivo.
Veamos un ejemplo clásico.
Factorial
const factorial = function(num) { debugger; if (num === 0 || num === 1) { return 1 } else { return num * factorial(num - 1) }}factorial(5)¡Aquí estamos tratando de encontrar 5! (cinco factorial). La función factorial se define como el producto de todos los enteros positivos menores o iguales a su argumento.
La primera condición dice: "si el parámetro pasado es igual a 0 o 1, saldremos y devolveremos 1".
A continuación, el caso recursivo dice:
"Si el parámetro no es 0 o 1, entonces pasaremos el valor de numveces el valor de retorno de llamar a esta función nuevamente con num-1su argumento".
Entonces, si llamamos factorial(0), la función devuelve 1 y nunca llega al caso recursivo.
Lo mismo vale para factorial(1).
Podemos ver lo que está sucediendo si insertamos una declaración de depuración en el código y usamos devtools para revisarla y observar la pila de llamadas.
- La pila de ejecución se coloca
factorial()con 5 cuando pasó el argumento. El caso base es falso, así que ingrese la condición recursiva. - La pila de ejecución se coloca
factorial()por segunda vez connum-1= 4 como argumento. El caso base es falso, ingrese la condición recursiva. - La pila de ejecución se coloca
factorial()por tercera vez connum-1(4–1) = 3 como argumento. El caso base es falso, ingrese la condición recursiva. - La pila de ejecución coloca
factorial()una cuarta vez connum-1(3–1) = 2 como argumento. El caso base es falso, ingrese la condición recursiva. - La pila de ejecución coloca
factorial()una quinta vez connum-1(2–1) = 1 como argumento. Ahora el caso base es verdadero, así que devuelve 1.
En este punto, hemos disminuido el argumento en uno en cada llamada de función hasta que alcancemos una condición para devolver 1.
6. A partir de aquí, el último contexto de ejecución se completa num === 1, por lo que la función devuelve 1.
7. A continuación num === 2, el valor devuelto es 2. (1 × 2).
8. A continuación num === 3, el valor de retorno es 6, (2 × 3).
Hasta ahora tenemos 1 × 2 × 3.
9. A continuación,, num === 4(4 × 6). 24 es el valor de retorno al siguiente contexto.
10. Finalmente, num === 5(5 × 24) y tenemos 120 como valor final.
La recursividad es bastante buena, ¿verdad?
Podríamos haber hecho lo mismo con un bucle for o while. Pero el uso de la recursividad produce una solución elegante que es más legible.
Por eso utilizamos soluciones recursivas.
Muchas veces, un problema dividido en partes más pequeñas es más eficiente. Dividir un problema en partes más pequeñas ayuda a superarlo. Por lo tanto, la recursividad es un enfoque de divide y vencerás para resolver problemas.
- Los subproblemas son más fáciles de resolver que el problema original
- Las soluciones a los subproblemas se combinan para resolver el problema original.
“Divide y vencerás” se usa con mayor frecuencia para recorrer o buscar estructuras de datos, como árboles de búsqueda binaria, gráficos y montones. También funciona para muchos algoritmos de clasificación, como clasificación rápida y clasificación en pilas.
Trabajemos con los siguientes ejemplos. Utilice devtools para tener una idea conceptual de lo que está sucediendo, dónde y cuándo. Recuerde usar declaraciones del depurador y recorrer cada proceso.
Fibonacci
const fibonacci = function(num) { if (num <= 1) { return num } else { return fibonacci(num - 1) + fibonacci(num - 2) }}fibonacci(5);Matrices recursivas
function flatten(arr) { var result = [] arr.forEach(function(element) { if (!Array.isArray(element)) { result.push(element) } else { result = result.concat(flatten(element)) } }) return result}flatten([1, [2], [3, [[4]]]]);Invertir una cuerda
function reverse(str) { if (str.length === 0) return '' return str[str.length - 1] + reverse(str.substr(0, str.length - 1))}reverse('abcdefg');Ordenación rápida
function quickSort(arr, lo, hi) { if (lo === undefined) lo = 0 if (hi === undefined) hi = arr.length - 1 if (lo partition: ' + p) // sort subarrays quickSort(arr, lo, p - 1) quickSort(arr, p + 1, hi) } // for initial call, return a sorted array if (hi - lo === arr.length - 1) return arr} function partition(arr, lo, hi) { // choose last element as pivot var pivot = arr[hi] // keep track of index to put pivot at var pivotLocation = lo // loop through subarray and if element <= pivot, place element before pivot for (var i = lo; i < hi; i++) { if (arr[i] <= pivot) { swap(arr, pivotLocation, i) pivotLocation++ } } swap(arr, pivotLocation, hi) return pivotLocation}function swap(arr, index1, index2) { if (index1 === index2) return var temp = arr[index1] arr[index1] = arr[index2] arr[index2] = temp console.log('swapped' + arr[index1], arr[index2], +' in ', arr) return arr}quickSort([1, 4, 3, 56, 9, 8, 7, 5])Es importante practicar técnicas recursivas. Para estructuras de datos anidadas como árboles, gráficos y montones, la recursividad es invaluable.
En un artículo futuro, discutiré las técnicas de memorización y optimización de llamadas finales en lo que respecta a la recursividad. ¡Gracias por leer!
Recursos adicionales
Wikipedia
Ingeniería de software
Otro buen articulo
Material didáctico abierto del MIT