Introdução
Recursão em cauda
Uma função é recursiva em cauda se a última coisa executada pela função é uma chamada a si mesma.
Toda vez que uma função é chamada, um stack frame com suas variáveis locais e seus argumentos é colocado no topo da pilha de chamadas de função.
Quando a função retorna, o stack frame é removido da pilha.
Funções recursivas em cauda permitem a otimização de chamada em cauda (ou eliminação de chamada em cauda).
É uma otimização que permite reutilizar o último stack frame na próxima chamada de função, quando é garantido que a função anterior não vai mais precisar dele.
Isso reduz a preocupação com o estouro da pilha de chamadas de função, que é a situação em que há tantos frames na pilha que não sobra memória para criar mais um.
Otimização de chamada em cauda em Elm
Sob certas condições, o compilador de Elm é capaz de realizar automaticamente uma otimização de chamada em cauda ao compilar para JavaScript.
A otimização pode acontecer em uma função recursiva quando a última operação de um ramo é feita chamando a própria função em uma aplicação de função simples.
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 em 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 em cauda e será otimizada, porque a última operação do ramo else é factorialHelper chamando a si mesma.
Isso não seria possível em uma função com a assinatura de tipo Int -> Int e, na prática, a otimização de chamada em cauda costuma ser obtida definindo funções auxiliares.
Instruções
Piper é uma ávida confeiteira de tortas.
Ninguém sabe se ela começou a fazer tortas por causa do próprio nome, ou se mudou de nome para combinar com o hobby.
À primeira vista, a segunda opção não parece muito provável, mas veja bem, Piper é completamente fascinada por tortas.
Ela está sempre mexendo na cozinha, ajustando suas receitas, aperfeiçoando sua arte, para a alegria absoluta de seus amigos.
O interesse mais recente dela?
Fazer tortas o mais circulares possível, a ponto da perfeição matemática, com a ajuda do seu número favorito, você adivinhou: π.
Piper encontrou uma fórmula encantadora para calcular π iterativamente, a Transformação de Convergência de Newton/Euler:
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Ajude Piper a assar sua torta matematicamente perfeita calculando π.
1. Fatorial
Vamos aquecer primeiro.
O operador fatorial, geralmente escrito !, é definido como
0! = 1
n! = 1 * 2 * 3 * ... * n
Defina a função factorial, que vai calcular o fatorial de forma recursiva em cauda.
factorial 4
-- 24
2. Fatorial Duplo
O operador fatorial duplo, geralmente escrito !!, é definido como
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
Defina a função doubleFactorial, que vai calcular o fatorial de forma recursiva em cauda.
factorial 5
-- 15
factorial 6
-- 48
Defina a função pipersPi, que vai aproximar π usando um número definido de termos da fórmula da Transformação de Convergência de Newton/Euler de forma recursiva em cauda.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Vamos calcular o primeiro termo.
Para um limite superior de 0 (em vez de infinito), temos:
π / 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
