Recursión y recursión de cola en Kotlin

En este artículo, aprenderá a crear funciones recursivas. Una función que se llama a sí misma. Además, también aprenderá sobre las funciones de recursión de cola.

llamada a sí mismaFunciónSe llama a la función recursiva. Y esta técnica se llama recursión.

Un ejemplo físico es poner dos espejos paralelos uno al lado del otro. Cualquier objeto entre ellos será reflejado recursivamente.

¿Cómo funciona la recursión en la programación?

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

Aquí, se llama a la función recurse() desde el cuerpo propio de la función recurse(). El funcionamiento de este programa es el siguiente:

Aquí, la llamada recursiva sigue en perpetuidad, lo que lleva a una recursión infinita.

Para evitar la recursión infinita, se puede usar una rama de recursión mientras que en otras ramas no se realiza recursión.if ... else(o un método similar).

Ejemplo: buscar el factorial de un número usando recursión

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

Al ejecutar este programa, la salida es:

4　Factorial =　24

¿Cómo funciona este programa?

La siguiente imagen de factorial() ilustra las llamadas recursivas de esta función:

Los pasos involucrados son los siguientes:

factorial(4)　　　　　　　　　　　　　　//　el1llamada a la función, parámetros:　4
4*factorial(3)　　　　　　　　　　　　//　el2llamada a la función, parámetros:　3
4*(3*factorial(2))　　　　　　　　//　el3llamada a la función, parámetros:　2
4*(3*(2*factorial(1))　　　　//　el4llamada a la función, parámetros:　1　
4*(3*(2*1))　　　　　　　　　　　　　　　　　
24

Recursión de cola en Kotlin

La recursión de cola no es una característica del lenguaje Kotlin, sino un concepto general. Algunos lenguajes de programación, incluyendo Kotlin, lo utilizan para optimizar las llamadas recursivas, mientras que otros lenguajes (como Python) no las admiten.

¿Qué es la recursión de cola?

En la recursión normal, primero se realizan todas las llamadas recursivas y luego se calcula el resultado según el valor de retorno (como se muestra en el ejemplo anterior). Por lo tanto, no obtendrá un resultado antes de realizar todas las llamadas recursivas.

En la recursión de cola, primero se realiza el cálculo y luego se realiza la llamada recursiva (la llamada recursiva pasa el resultado actual del paso al siguiente llamado recursivo). Esto hace que la llamada recursiva sea equivalente a un ciclo y evita el riesgo de desbordamiento de pila.

Condiciones de la recursión de cola

Si la llamada a la función propia es la última operación que ejecuta, entonces esta función recursiva puede realizar recursión de cola. Por ejemplo,

Ejemplo1:No cumple con las condiciones de recursión final, ya que la llamada a la función 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)　　　　　
　　　　}
}

Ejemplo2:Cumple con las condiciones de recursión final, ya que la llamada a la función 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 informar al compilador de que se debe ejecutar la recursión final en Kotlin, debe marcar la función con el modificador tailrec.

Ejemplo: Recursión final

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)
}

Al ejecutar este programa, la salida es:

354224848179261915075

Este programa calcula el elemento100 elementos. Porque la salida puede ser un entero muy grande, hemos importado la clase BigInteger de la biblioteca estándar de Java.

En este caso, la función fibonacci() está marcada con el modificador trarec, lo que qualifica a la función para llamadas de recursión final. Por lo tanto, el compilador optimiza la recursión en este caso.

Si intenta encontrar el elemento20000 elementos (o cualquier otro entero grande), el compilador lanzará la excepción java.lang.StackOverflowError.
Sin embargo, nuestro programa anterior funciona bien. Esto se debe a que hemos utilizado la recursión final, que utiliza una versión eficiente basada en bucles en lugar de la recursión tradicional.

Ejemplo: Factorial con recursión final

El ejemplo anterior (el primer ejemplo) que se utiliza para calcular el factorial de un número no puede optimizarse para la recursión final. Este es otro programa que realiza la misma tarea.

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

Al ejecutar este programa, la salida es:

5　Factorial=　120

El compilador puede optimizar la recursión en este programa porque las funciones recursivas pueden realizar recursión de cola y hemos utilizado el modificador tailrec para informar al compilador de que optimice la recursión.