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 en la parte superior de la pila de llamadas.
Cuando una función devuelve, el marco de pila se elimina 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 en la siguiente llamada a una función cuando se garantiza que la función anterior ya no lo necesita.
Esto reduce el riesgo de desbordar la pila de llamadas, una situación en la que hay tantos marcos en la pila de llamadas que ya no queda memoria para crear otro más.
Optimización de llamadas de cola en Elm
En determinadas condiciones, el compilador de Elm puede realizar automáticamente una optimización de llamadas de cola al compilar a JavaScript.
La optimización puede darse en una función recursiva cuando la última operación de una rama consiste en llamar a la propia función en 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 anterior 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 anterior 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 en una función con la firma de tipo Int -> Int y, en la práctica, la optimización de llamadas de cola suele lograrse definiendo funciones auxiliares.
Instrucciones
Piper es una entusiasta de hacer tartas.
Nadie sabe si empezó a hacer tartas por su nombre o si se cambió el nombre para que coincidiera con su afición.
A primera vista, lo segundo no parece muy probable, pero verás, a Piper le fascinan las tartas.
Siempre está trasteando en la cocina, ajustando sus recetas, mejorando su técnica, para deleite absoluto de sus amigos.
¿Su último interés?
Hacer tartas lo más circulares posible, hasta alcanzar la perfección matemática, con la ayuda de su número favorito, lo has adivinado: π.
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 tarta matemáticamente perfecta calculando π.
1. Factorial
Primero, vamos a calentar.
El operador factorial, que normalmente se escribe !, se define así
0! = 1
n! = 1 * 2 * 3 * ... * n
Define la función factorial, que calculará el factorial de forma recursiva de cola.
factorial 4
-- 24
2. Doble factorial
El operador doble factorial, que normalmente 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 de forma recursiva de cola.
factorial 5
-- 15
factorial 6
-- 48
Define la función pipersPi, que aproximará π usando un número determinado de términos de la fórmula de la transformación de convergencia de Newton/Euler, de forma recursiva 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
