Hola Habr!
Hoy continuamos nuestra investigación sobre programación funcional en el contexto de EcmaScript, cuya especificación se basa en JavaScript. En los artículos anteriores del ciclo, se consideraron los siguientes temas:
- Funciones puras, lambdas, inmunidad.
- Composición, Curry, Aplicación Parcial
Recursividad
Como siempre, Wikipedia nos ayuda a encontrar una definición:
Recursión: la definición, descripción, imagen de un objeto o proceso dentro de este objeto o proceso en sí mismo, es decir, la situación cuando el objeto es parte de sí mismo. El término "recursión" se utiliza en varios campos especiales de conocimiento, desde la lingüística hasta la lógica, pero encuentra la mayor aplicación en matemáticas y ciencias de la computación.
Para la programación, la recursividad se refiere a
procesos que se invocan en sus cuerpos . Una función recursiva tiene varios componentes obligatorios:
- Condición terminal - condición de terminación
- La regla que se mueve profundamente en la recursividad
Considere el ejemplo más popular de recursión: el cálculo factorial.
const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); }
Distinguimos los componentes característicos de una función recursiva. Condición terminal
if (n === 0) { return 1; }
y regla de recursión
return n * factorial(n - 1);
Es importante darse cuenta de que la recursividad no es una característica específica de JS, sino una técnica muy común en la programación.
Procesos recursivos e iterativos.
La recursión se puede organizar de dos maneras: a través de un proceso recursivo o iterativo.
Ya hemos visto el proceso recursivo:
const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); }
Una solución iterativa al problema factorial se vería así:
const factorial = (n) => { const iter = (counter, acc) => { if (counter === 1) { return acc; } return iter(counter - 1, counter * acc); }; return iter(n, 1); };
Ambas opciones son recursivas. Ambas soluciones tienen características propias de la recursividad: la condición terminal y la regla de movimiento a lo largo de la recursividad. Veamos sus diferencias.
El proceso recursivo en cada paso recuerda la acción. lo que hay que hacer Habiendo alcanzado las condiciones térmicas, realiza todas las acciones recordadas en el orden inverso. Vamos a ilustrar con un ejemplo. Cuando el proceso recursivo considera el factorial 6, entonces necesita recordar 5 números para contarlos al final, cuando no puede llegar a ningún lado y ya no puede moverse recursivamente hacia las profundidades. Cuando estamos en la siguiente llamada de función, en algún lugar fuera de esta llamada, estos números recordados se almacenan en la memoria.
Se parece a esto:
factorial(3);
Como puede ver, la idea básica de un proceso recursivo es posponer el cálculo hasta el final.
Dicho proceso genera
un estado variable en el tiempo que se almacena "en algún lugar" fuera de la llamada a la función actual.
Creo que recuerdas que en el primer artículo de la serie sobre
Programación funcional, hablamos sobre la importancia de la inmunidad y la falta de estado. Tener una afección da lugar a muchos problemas que no siempre son fáciles de manejar.
Un proceso iterativo difiere de
uno recursivo en un número fijo de estados. En cada paso, el proceso iterativo considera todo lo que puede calcular, por lo que cada paso de la recursión existe independientemente del anterior.
Se ve así:
iter(3, 1);
Creo que es obvio que un proceso iterativo consume menos memoria. Por lo tanto, siempre debe usarlo al crear una recursión. La única excepción: si no podemos calcular el valor hasta que se alcance la condición térmica.
Árbol de recursión
Mucha gente piensa que los árboles y trabajar con ellos es algo muy abstruso, complejo e incomprensible para los simples mortales. Este no es realmente el caso. Cualquier estructura jerárquica se puede representar en forma de árbol. Incluso el pensamiento humano es como un árbol.
Para comprender mejor la recursividad de los árboles, echemos un vistazo a un ejemplo simple y popular: los números de Fibonacci.
Números de Fibonacci: elementos de una secuencia numérica 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, ... (secuencia A000045 en OEIS), en el que los dos primeros números son 1 y 1, o 0 y 1, y cada número posterior es igual a la suma de los dos números anteriores. Lleva el nombre del matemático medieval Leonardo de Pisa (conocido como Fibonacci).
Matemáticamente, es bastante simple formular una descripción (y la programación declarativa es la descripción) de esta secuencia:
fib(n) = [ 0 n = 0,//(1) 1 n = 1,//(2) fib(n-1) + fib(n-2) ]
Ahora pasemos de las matemáticas al razonamiento lógico (después de todo, necesitamos escribir la lógica del programa). Para calcular fib (5), tenemos que calcular fib (4) y fib (3). Para calcular fib (4), tenemos que calcular fib (3) y fib (2). Para calcular fib (3), tenemos que calcular fib (2) y así sucesivamente hasta llegar a los valores conocidos (1) y (2) en nuestro modelo matemático.
¿A qué pensamientos debería llevarnos nuestro razonamiento? Obviamente, debemos usar la recursividad. La condición térmica se puede formular como n <= 1. Sin embargo, en lugar de una rama de recursión (como en los ejemplos anteriores), tendremos dos ramas: fib (n-1), fib (n-2).
const fib = (n) => (n <= 1 ? n : fib(n - 1) + fib(n - 2));
Esta solución tiene un significativo menos! Considera el resultado del mismo valor de n varias veces en diferentes ramas. Para resolver este problema, existe una técnica de programación funcional llamada
memorización , de la que hablamos en uno de los siguientes artículos.
Conclusión
La recursión es una herramienta de programación muy poderosa. Permítame recordarle que, por regla general, utilizamos un proceso iterativo. Vale la pena usar un proceso recursivo solo si no podemos calcular el resultado intermedio en cada paso de la recursividad.