Introducción
Recursión de cola
Una función es recursiva de cola si lo último que ejecuta la función es una llamada a sí misma.
Cada vez que se llama a una función, se coloca un marco de pila con sus variables locales y sus argumentos encima de la pila de llamadas de funciones.
Cuando una función devuelve, el marco de pila se quita de la pila.
Las funciones recursivas de cola permiten la optimización de llamadas de cola (o eliminación de llamadas de cola).
Es una optimización que permite reutilizar el último marco de pila para la siguiente llamada a función cuando la función anterior tiene garantizado que ya no lo necesitará.
Esto mitiga la preocupación de desbordar la pila de llamadas de funciones, que es una situación en la que hay tantos marcos en la pila de llamadas que ya no queda memoria para crear otro.
Optimización de llamadas de cola en Elm
Bajo cierta condición, el compilador de Elm puede realizar automáticamente una optimización de llamadas de cola al compilar a JavaScript.
La optimización puede ocurrir en una función recursiva cuando la última operación de una rama consiste en llamar a la función misma mediante una aplicación de función simple.
Veamos algunos ejemplos:
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
La implementación de arriba no es recursiva de cola, porque la última operación de la rama else es una multiplicación n *.
factorial : Int -> Int
factorial n =
factorialHelper n n
factorialHelper : Int -> Int -> Int
factorialHelper n resultSoFar =
if n <= 1 then
resultSoFar
else
factorialHelper (n-1) (n * resultSoFar)
La implementación de arriba es recursiva de cola y se optimizará, porque la última operación de la rama else es factorialHelper llamándose a sí misma.
Esto no sería posible para una función con la firma de tipo Int -> Int, y en la práctica la optimización de llamadas de cola a menudo se logra definiendo funciones auxiliares.
Instrucciones
Piper es una apasionada de hornear pasteles.
Nadie sabe si eligió hornear pasteles por su nombre, o si se cambió el nombre para que coincidiera con su pasatiempo. A simple vista, esto último no parece muy probable, pero verás: a Piper le fascinan los pasteles por completo. Siempre está experimentando en la cocina, ajustando sus recetas y mejorando su técnica, para deleite absoluto de sus amigos.
¿Su interés más reciente? Hornear pasteles lo más circulares posible, hasta alcanzar la perfección matemática, con la ayuda de su número favorito, ya lo adivinaste: π.
Piper encontró una fórmula maravillosa para calcular π de forma iterativa: la transformación de convergencia de Newton/Euler.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Ayuda a Piper a hornear su pastel matemáticamente perfecto calculando π.
1. Factorial
Primero, vamos a calentar motores.
El operador factorial, que por lo general se escribe !, se define así:
0! = 1
n! = 1 * 2 * 3 * ... * n
Define la función factorial, que calculará el factorial mediante recursión de cola.
factorial 4
-- 24
2. Doble factorial
El operador doble factorial, que por lo general se escribe !!, se define así:
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
Define la función doubleFactorial, que calculará el factorial mediante recursión de cola.
factorial 5
-- 15
factorial 6
-- 48
Define la función pipersPi, que aproximará π usando una cantidad determinada de términos de la fórmula de la transformación de convergencia de Newton/Euler, mediante recursión de cola.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Calculemos juntos el primer término.
Para un límite superior de 0 (en lugar de infinito), obtenemos:
π / 2 ≈ Sum for k from 0 to 0 of ( k! ) / ( 2 * k + 1 )!!
π / 2 ≈ ( 0! ) / ( 2 * 0 + 1 )!!
π / 2 ≈ 0! / 0!!
π / 2 ≈ 1 / 1
π / 2 ≈ 1
π ≈ 2
Cada término adicional mejorará la aproximación.
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
Ejercicio de aprendizaje
