Scala - Explicando Tail Recursion

Função tail recursive: é uma função que tem como última execução uma chamada para ela mesma. Um jeito mais fácil de entender tail recursion seria explicando com um exemplo:

Vamos escrever uma simples função que calcula o fatorial de um número. Bom se você não sabe o que é um fatorial, é simples, apenas multiplique o número pelo seu número anterior, exemplo: 5! (Fatorial de 5)   5 x 4 x 3 x 2 x 1 = 120. Resolvendo isto em Scala:

A função acima, não é uma função tail recursive, por quê? Porque não tem como última chamada ela mesma. Chamando a função acima, a execução seria da seguinte maneira:

> fatorial(3)
> 3 * fatorial(2)
> 3 * 2 * fatorial(1)
> 3 * 2 * 1 * fatorial(0)
> 3 * 2 * 1 * 0
> 6



A função acima, é uma função tail recursive, por quê? Porque executa por último uma chamada a ela mesma. Chamando a função acima, a execução seria da seguinte forma

> fatorial(3)
> loop(1,3)
> loop(3,2)
> loop(6,1)
> loop(6,0)
> 6

A vantagem de possuirmos uma função tail recursive, é que a cada execução do fatorial é usado o mesmo stack frame com os valores da pilha atualizados.

Você deve estar se perguntando se você deve sempre usar função tail recursion, na realidade não, apenas quando você possui uma função que irá executar milhares de vezes, evitando assim uma exceção de stackoverflow. Priorize uma função que seja fácil de entender.