Recursão e Recursão de Cauda no Kotlin

Neste artigo, você aprenderá a criar funções recursivas. Uma função que se chama a si mesma. Além disso, você também aprenderá sobre funções tail-recursive.

que chama a si mesmaFunçãoChamado de função recursiva. E essa técnica é chamada de recursão.

Um exemplo físico é posicionar dois espelhos paralelos uns ao outros. Qualquer objeto entre eles será refletido recursivamente.

Como a recursão funciona em programação?

fun main(args: Array<String>) {
　　　　... .. ...
　　　　recurse()
　　　　... .. ...
}
fun recurse() {
　　　　... .. ...
　　　　recurse()
　　　　... .. ...
}

Aqui, a chamada de função recurse() é feita a partir do corpo da própria função recurse(). O funcionamento do programa é o seguinte:

Aqui, a chamada recursiva continua para sempre, resultando em recursão infinita.

Para evitar recursão infinita, pode-se usar chamadas recursivas em uma ramificação e não recursivas em outras.if ... else(ou método semelhante).

Exemplo: usar recursão para encontrar o fatorial de um número

fun main(args: Array<String>) {
　　　　val　number　=　4
　　　　val result: Long
　　　　result = factorial(number)
　　　　println("$number Fatorial = $result")
}
fun factorial(n: Int): Long {
　　　　return　if　(n　==　1) toLong() else n*factorial(n-1)
}

Quando você executar este programa, a saída será:

4　Fatorial =　24

Como o programa funciona?

A figura a seguir ilustra a chamada recursiva da função factorial():

Os passos envolvidos são os seguintes:

factorial(4)　　　　　　　　　　　　　　//　o1a próxima chamada de função, parâmetros:　4
4*factorial(3)　　　　　　　　　　　　//　o2a próxima chamada de função, parâmetros:　3
4*(3*factorial(2))　　　　　　　　//　o3a próxima chamada de função, parâmetros:　2
4*(3*(2*factorial(1))　　　　//　o4a próxima chamada de função, parâmetros:　1　
4*(3*(2*1))　　　　　　　　　　　　　　　　　
24

Tail-recursive no Kotlin

Tail-recursive não é uma característica do Kotlin, mas um conceito geral. Alguns linguagens de programação, incluindo o Kotlin, usam isso para otimizar chamadas recursivas, enquanto outras linguagens (como o Python) não as suportam.

O que é tail-recursive?

Na recursão comum, primeiro são executadas todas as chamadas recursivas, e em seguida, são calculados os resultados com base nos valores de retorno (como mostrado no exemplo acima). Portanto, você não obterá o resultado antes de todas as chamadas recursivas.

No tail-recursive, primeiro é executada a computação, e em seguida, a chamada recursiva (a chamada recursiva passa o resultado atual para a próxima chamada recursiva). Isso torna a chamada recursiva equivalente a um loop, evitando o risco de estouro da pilha.

Condições de tail-recursive

Se a chamada de função própria for a última operação executada, a função recursiva pode ser tail-recursive. Por exemplo,

Exemplo1:Não cumpre as condições de recorrência terminal, porque a chamada de função n*factorial(n-1) não é a última operação.

fun factorial(n: Int): Long {
　　　　if (n ==　1) {
　　　　　　　　return n.toLong()
　　　　} else {
　　　　　　　　return n*factorial(n　-　1)　　　　　
　　　　}
}

Exemplo2:Cumpre as condições de recorrência terminal, porque a chamada de função fibonacci(n-1, a+b, a) é a última operação.

fun fibonacci(n: Int, a: Long, b: Long): Long {
　　　　return if (n == 0) b else fibonacci(n-1, a+, b, a)
}

Para informar ao compilador que a recorrência terminal será executada em Kotlin, você precisa marcar a função com o modificador tailrec.

Exemplo: Recorrência terminal

import java.math.BigInteger
fun main(args: Array<String>) {
　　　　val n =　100
　　　　val first = BigInteger("0")
　　　　val second = BigInteger("1")
　　　　println(fibonacci(n, first, second))
}
tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger {
　　　　return if (n == 0) a else fibonacci(n-1, b, a+b)
}

Quando você executar este programa, a saída será:

354224848179261915075

Este programa calcula o100 itens. Porque a saída pode ser um número inteiro muito grande, importamos a classe BigInteger da biblioteca padrão do Java.

Aqui, a função fibonacci() é marcada com o modificador trarec, a função tem direito a chamadas de recorrência terminal. Portanto, o compilador otimizou a recorrência neste caso.

Se você tentar encontrar o20000 itens (ou qualquer outro grande número inteiro), o compilador lançará a exceção java.lang.StackOverflowError.
Mas, nosso programa acima está funcionando bem. Isso é porque usamos recorrência terminal, que usa uma versão eficiente baseada em laço, em vez da recorrência tradicional.

Exemplo: Fatorial com recorrência terminal

No exemplo acima (o primeiro exemplo), o exemplo usado para calcular o fatorial de um número não pode ser otimizado para recorrência terminal. Este é outro programa para executar a mesma tarefa.

fun main(args: Array<String>) {
　　　　val　number　=　5
　　　　println("$number　fatorial　=　${factorial(number)}")
}
tailrec　fun　factorial(n:　Int,　run:　Int　=　1):　Long　{
　　　　return　if　(n　==　1)　run.toLong()　else　factorial(n-1,　run*n)
}

Quando você executar este programa, a saída será:

5　Fatorial =　120

O compilador pode otimizar a recursão neste programa, pois a função recursiva pode fazer recursão de cauda e usamos o modificador tailrec para informar ao compilador que otimize a recursão.