Recursion et recursion finale en Kotlin

Dans cet article, vous apprendrez à créer des fonctions récursives. Une fonction auto-appelante. De plus, vous découvrirez les fonctions récursives en queue.

appelle-toiFonctionIl s'agit d'une fonction récursive. Et cette technique s'appelle la récursion.

Un exemple physique est de placer deux miroirs parallèles les uns à côté des autres. Tout objet entre eux sera réflexion récursive.

Comment la récursion fonctionne-t-elle en programmation ?

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

Dans ce cas, l'appel de la fonction recurse() se fait à partir du corps même de la fonction recurse(). Le principe de fonctionnement de ce programme est le suivant :

Dans ce cas, l'appel récursif continue à s'exécuter indéfiniment, entraînant une récursion infinie.

Pour éviter la récursion infinie, il est possible d'utiliser une branche pour l'appel récursif et l'autre branche ne s'appelle pas récursivement.if ... else(ou méthode similaire).

Exemple : utiliser la récursion pour trouver la factorielle d'un nombre

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

Lorsque ce programme est exécuté, la sortie est :

4　Factorielle =　24

Comment ce programme fonctionne-t-il ?

factorial() montre comment la fonction effectue des appels récursifs :

Les étapes impliquées sont les suivantes :

factorial(4)　　　　　　　　　　　　　　//　le1l'appel de fonction suivant, paramètres:　4
4*factorial(3)　　　　　　　　　　　　//　le2l'appel de fonction suivant, paramètres:　3
4*(3*factorial(2))　　　　　　　　//　le3l'appel de fonction suivant, paramètres:　2
4*(3*(2*factorial(1))　　　　//　le4l'appel de fonction suivant, paramètres:　1　
4*(3*(2*1))　　　　　　　　　　　　　　　　　
24

Récursion en queue Kotlin

La récursion en queue n'est pas une caractéristique du langage Kotlin, mais un concept universel. Certains langages de programmation, y compris Kotlin, l'utilisent pour optimiser les appels récursifs, tandis que d'autres langages (par exemple Python) ne les supportent pas.

Qu'est-ce que la récursion en queue ?

Dans la récursion ordinaire, d'abord effectuer tous les appels récursifs, puis calculer le résultat en fonction des valeurs de retour (comme dans l'exemple ci-dessus). Donc, vous ne recevrez pas de résultat avant d'effectuer tous les appels récursifs.

Dans la récursion en queue, d'abord effectuer les calculs, puis effectuer l'appel récursif (l'appel récursif transmet le résultat actuel à l'appel récursif suivant). Cela rend l'appel récursif équivalent à une boucle, et évite le risque de débordement de pile.

Conditions de la récursion en queue

Si l'appel de fonction à soi-même est la dernière opération qu'il effectue, cette fonction récursive peut effectuer une récursion en queue. Par exemple,

Exemple1:ne répond pas aux conditions de récursion terminale, car l'appel de la fonction自身 n*factorial(n-1) n'est pas l'opération finale.

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

Exemple2:elle répond aux conditions de récursion terminale, car l'appel de la fonction自身fibonacci(n-1, a+b, a) est l'opération finale.

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

Pour informer le compilateur que la récursion terminale est utilisée en Kotlin, vous devez marquer la fonction avec le modificateur tailrec.

Exemple : Récursion terminale

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

Lorsque ce programme est exécuté, la sortie est :

354224848179261915075

Ce programme calcule le100ème élément. Comme la sortie peut être un grand nombre, nous importons la classe BigInteger de la bibliothèque standard de Java.

Dans ce cas, la fonction fibonacci() est marquée avec le modificateur trarec, ce qui la qualifie pour une optimisation de récursion. Par conséquent, le compilateur optimise la récursion dans ce cas.

Si vous essayez de trouver le20000ème élément (ou tout autre grand nombre), le compilateur lève une exception java.lang.StackOverflowError.
Cependant, notre programme ci-dessus fonctionne bien. Cela est dû à l'utilisation de la récursion terminale, qui utilise une version efficace basée sur la boucle, plutôt que la récursion traditionnelle.

Exemple : Factoriel avec récursion terminale

Dans cet exemple (le premier exemple) utilisé pour calculer le factoriel d'un nombre, l'optimisation pour la récursion terminale n'est pas possible. Voici un autre programme pour effectuer la même tâche.

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

Lorsque ce programme est exécuté, la sortie est :

5　Factorielle=　120

Le compilateur peut optimiser la récursion dans ce programme car les fonctions récursives peuvent effectuer une récursion finale, et nous avons utilisé le modificateur tailrec pour informer le compilateur d'optimiser la récursion.