Introdução
Recursão de cauda
Uma função é recursiva de cauda se a última coisa executada pela função for uma chamada a si própria.
Sempre que se chama uma função, é colocado um frame da pilha, com as suas variáveis locais e os seus argumentos, no topo da pilha de chamadas de funções.
Quando uma função devolve, o frame da pilha é removido da pilha.
As funções recursivas de cauda permitem a otimização de chamadas de cauda (ou eliminação de chamadas de cauda).
É uma otimização que permite reutilizar o último frame da pilha pela chamada de função seguinte, quando há a garantia de que a função anterior já não precisa dele.
Isto atenua o problema de transbordar a pilha de chamadas de funções, que é a situação em que há tantos frames na pilha de chamadas de funções que já não sobra memória para criar outro.
Otimização de chamadas de cauda em Elm
Sob certas condições, o compilador de Elm consegue realizar automaticamente uma otimização de chamadas de cauda ao compilar para JavaScript.
A otimização pode acontecer numa função recursiva quando a última operação de um ramo é feita chamando a própria função numa aplicação simples de função.
Vamos ver alguns exemplos:
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
A implementação acima não é recursiva de cauda, porque a última operação do ramo else é uma multiplicação, 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)
A implementação acima é recursiva de cauda e será otimizada, porque a última operação do ramo else é o factorialHelper a chamar-se a si próprio.
Isto não seria possível numa função com a assinatura de tipo Int -> Int e, na prática, a otimização de chamadas de cauda consegue-se muitas vezes definindo funções auxiliares.
Instruções
A Piper é uma apaixonada por fazer tartes.
Ninguém sabe se começou a fazer tartes por causa do nome, ou se mudou de nome para combinar com o passatempo.
À primeira vista, a segunda hipótese não parece muito provável, mas repara: a Piper é absolutamente fascinada por tartes.
Está sempre a mexer na cozinha, a ajustar as receitas, a aperfeiçoar a arte, para grande satisfação dos seus amigos.
O interesse mais recente dela?
Fazer tartes o mais circulares possível, ao ponto da perfeição matemática, com a ajuda do seu número preferido, já adivinhaste: π.
A Piper encontrou uma fórmula encantadora para calcular π de forma iterativa, a Transformação de Convergência de Newton/Euler:
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Ajuda a Piper a fazer a sua tarte matematicamente perfeita, calculando π.
1. Fatorial
Vamos aquecer primeiro.
O operador fatorial, normalmente escrito !, define-se como
0! = 1
n! = 1 * 2 * 3 * ... * n
Define a função factorial, que vai calcular o fatorial de forma recursiva de cauda.
factorial 4
-- 24
2. Fatorial Duplo
O operador fatorial duplo, normalmente escrito !!, define-se como
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
Define a função doubleFactorial, que vai calcular o fatorial de forma recursiva de cauda.
factorial 5
-- 15
factorial 6
-- 48
Define a função pipersPi, que vai aproximar π usando um número fixo de termos da fórmula da Transformação de Convergência de Newton/Euler, de forma recursiva de cauda.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Vamos calcular o primeiro termo juntos.
Para um limite superior de 0 (em vez de infinito), obtemos:
π / 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 termo extra melhora a aproximação.
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
Exercício de aprendizagem
