En este artículo, aprenderá a crear funciones recursivas; una función que se llama a sí misma. Además, aprenderá sobre la función recursiva de cola.
Una función que se llama a sí misma se conoce como función recursiva. Y esta técnica se conoce como recursividad.
Un ejemplo del mundo físico sería colocar dos espejos paralelos uno frente al otro. Cualquier objeto entre ellos se reflejaría de forma recursiva.
¿Cómo funciona la recursividad en la programación?
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Aquí, la recurse()función se llama desde el propio cuerpo de la recurse()función. Así es como funciona este programa:
Aquí, la llamada recursiva continúa para siempre provocando una recursión infinita.
Para evitar la recursividad infinita, if … else (o un enfoque similar) se puede usar donde una rama hace la llamada recursiva y otra no.
Ejemplo: encontrar factorial de un número usando recursividad
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) )
Cuando ejecute el programa, la salida será:
Factorial de 4 = 24
¿Cómo funciona este programa?
La llamada recursiva de la factorial()función se puede explicar en la siguiente figura:
Estos son los pasos involucrados:
factorial (4) // 1ª llamada a función. Argumento: 4 4 * factorial (3) // 2ª llamada a función. Argumento: 3 4 * (3 * factorial (2)) // 3ª llamada a función. Argumento: 2 4 * (3 * (2 * factorial (1))) // 4ª llamada a función. Argumento: 1 4 * (3 * (2 * 1)) 24
Recursión de la cola de Kotlin
La recursividad de la cola es un concepto genérico en lugar de la característica del lenguaje Kotlin. Algunos lenguajes de programación, incluido Kotlin, lo utilizan para optimizar las llamadas recursivas, mientras que otros lenguajes (por ejemplo, Python) no los admiten.
¿Qué es la recursividad de la cola?
En la recursividad normal, primero realiza todas las llamadas recursivas y, al final, calcula el resultado de los valores devueltos (como se muestra en el ejemplo anterior). Por lo tanto, no obtiene el resultado hasta que se realizan todas las llamadas recursivas.
En la recursividad de cola, los cálculos se realizan primero, luego se ejecutan las llamadas recursivas (la llamada recursiva pasa el resultado de su paso actual a la siguiente llamada recursiva). Esto hace que la llamada recursiva sea equivalente a un bucle y evita el riesgo de desbordamiento de pila.
Condición para la recursividad de la cola
Una función recursiva es elegible para la recursividad de cola si la llamada a la función a sí misma es la última operación que realiza. Por ejemplo,
Ejemplo 1: No es elegible para la recursividad de cola porque la llamada a la función a sí misma n*factorial(n-1)no es la última operación.
fun factorial (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * factorial (n - 1)))
Ejemplo 2: Elegible para la recursividad de cola porque la llamada a la función a sí misma fibonacci(n-1, a+b, a)es la última operación.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Para decirle al compilador que realice la recursividad de cola en Kotlin, debe marcar la función con el tailrecmodificador.
Ejemplo: Tail Recursion
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) )
Cuando ejecute el programa, la salida será:
354224848179261915075
Este programa calcula el 100 º término de la serie de Fibonacci. Dado que la salida puede ser un entero muy grande, hemos importado la clase BigInteger de la biblioteca estándar de Java.
Aquí, la función fibonacci()está marcada con un tailrecmodificador y la función es elegible para la llamada recursiva de cola. Por tanto, el compilador optimiza la recursividad en este caso.
Si intenta encontrar el 20.000 º plazo (o cualquier otra gran número entero) de la serie de Fibonacci sin utilizar la recursión de cola, el compilador arrojará java.lang.StackOverflowErroruna excepción. Sin embargo, nuestro programa anterior funciona bien. Es porque hemos usado la recursividad de cola que usa una versión eficiente basada en bucles en lugar de la recursividad tradicional.
Ejemplo: factorial usando la recursividad de la cola
El ejemplo para calcular el factorial de un número en el ejemplo anterior (primer ejemplo) no se puede optimizar para la recursividad de la cola. Aquí hay un programa diferente para realizar la misma tarea.
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) )
Cuando ejecute el programa, la salida será:
Factorial de 5 = 120
El compilador puede optimizar la recursividad en este programa ya que la función recursiva es elegible para la recursividad de cola, y hemos usado un tailrecmodificador que le dice al compilador que optimice la recursividad.
