Neste artigo, você aprenderá a criar funções recursivas; uma função que chama a si mesma. Além disso, você aprenderá sobre a função recursiva da cauda.
Uma função que chama a si mesma é conhecida como função recursiva. E, esta técnica é conhecida como recursão.
Um exemplo de mundo físico seria colocar dois espelhos paralelos voltados um para o outro. Qualquer objeto entre eles seria refletido recursivamente.
Como funciona a recursão na programação?
fun main (args: Array) (… recurse () …) fun recurse () (… recurse () …)
Aqui, a recurse()função é chamada a partir do próprio corpo da recurse()função. Veja como funciona este programa:
Aqui, a chamada recursiva continua para sempre causando recursão infinita.
Para evitar a recursão infinita, if… else (ou abordagem semelhante) pode ser usado onde um branch faz a chamada recursiva e outro não.
Exemplo: Encontre o fatorial de um número usando recursão
fun main(args: Array) ( val number = 4 val result: Long result = factorial(number) println("Factorial of $number = $result") ) fun factorial(n: Int): Long ( return if (n == 1) n.toLong() else n*factorial(n-1) )
Quando você executa o programa, a saída será:
Fatorial de 4 = 24
Como funciona esse programa?
A chamada recursiva da factorial()função pode ser explicada na figura a seguir:
Aqui estão as etapas envolvidas:
fatorial (4) // 1ª chamada de função. Argumento: 4 4 * fatorial (3) // 2ª chamada de função. Argumento: 3 4 * (3 * fatorial (2)) // 3ª chamada de função. Argumento: 2 4 * (3 * (2 * fatorial (1))) // 4ª chamada de função. Argumento: 1 4 * (3 * (2 * 1)) 24
Kotlin Tail Recursion
A recursão de cauda é um conceito genérico, e não o recurso da linguagem Kotlin. Algumas linguagens de programação, incluindo Kotlin, usam-no para otimizar chamadas recursivas, enquanto outras linguagens (por exemplo, Python) não as suportam.
O que é recursão da cauda?
Na recursão normal, você executa todas as chamadas recursivas primeiro e, por fim, calcula o resultado dos valores de retorno (como mostrado no exemplo acima). Portanto, você não obtém o resultado até que todas as chamadas recursivas sejam feitas.
Na recursão final, os cálculos são executados primeiro, depois as chamadas recursivas são executadas (a chamada recursiva passa o resultado da sua etapa atual para a próxima chamada recursiva). Isso torna a chamada recursiva equivalente ao loop e evita o risco de estouro de pilha.
Condição para recursão da cauda
Uma função recursiva é elegível para recursão final se a chamada de função para si mesma for a última operação que ela executa. Por exemplo,
Exemplo 1: Não elegível para recursão n*factorial(n-1)final porque a chamada de função para si mesma não é a última operação.
fatorial divertido (n: Int): Longo (if (n == 1) (return n.toLong ()) else (return n * fatorial (n - 1)))
Exemplo 2: Elegível para recursão fibonacci(n-1, a+b, a)final porque a chamada de função para si mesma é 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 dizer ao compilador para realizar a recursão final no Kotlin, você precisa marcar a função com o tailrecmodificador.
Exemplo: Recursão de cauda
import java.math.BigInteger fun main(args: Array) ( 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ê executa o programa, a saída será:
354224848179261915075
Este programa calcula a 100 ª termo da série de Fibonacci. Visto que a saída pode ser um número inteiro muito grande, importamos a classe BigInteger da biblioteca padrão Java.
Aqui, a função fibonacci()é marcada com tailrecmodificador e a função é elegível para chamada recursiva final. Portanto, o compilador otimiza a recursão neste caso.
Se você tentar encontrar o 20000 th prazo (ou qualquer outro grande inteiro) da série de Fibonacci sem usar cauda recursão, o compilador irá lançar java.lang.StackOverflowErroruma exceção. No entanto, nosso programa acima funciona muito bem. É porque usamos a recursão de cauda, que usa uma versão baseada em loop eficiente em vez da recursão tradicional.
Exemplo: fatorial usando recursão de cauda
O exemplo para calcular o fatorial de um número no exemplo acima (primeiro exemplo) não pode ser otimizado para recursão de cauda. Aqui está um programa diferente para realizar a mesma tarefa.
fun main(args: Array) ( val number = 5 println("Factorial of $number = $(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ê executa o programa, a saída será:
Fatorial de 5 = 120
O compilador pode otimizar a recursão neste programa, pois a função recursiva é elegível para recursão final, e usamos um tailrecmodificador que diz ao compilador para otimizar a recursão.
