Dans cet article, vous apprendrez à créer des fonctions récursives; une fonction qui s'appelle elle-même. En outre, vous découvrirez la fonction récursive de queue.
Une fonction qui s'appelle elle-même est appelée fonction récursive. Et cette technique est connue sous le nom de récursivité.
Un exemple de monde physique serait de placer deux miroirs parallèles face à face. Tout objet entre eux serait reflété récursivement.
Comment fonctionne la récursivité en programmation?
fun principal (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Ici, la recurse()fonction est appelée à partir du corps de la recurse()fonction elle-même. Voici comment fonctionne ce programme:
Ici, l'appel récursif continue indéfiniment provoquant une récursion infinie.
Pour éviter une récursion infinie, if… else (ou une approche similaire) peut être utilisée là où une branche effectue l'appel récursif et l'autre non.
Exemple: trouver la factorielle d'un nombre à l'aide de la récursivité
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) )
Lorsque vous exécutez le programme, la sortie sera:
Factorielle de 4 = 24
Comment fonctionne ce programme?
L'appel récursif de la factorial()fonction peut être expliqué dans la figure suivante:
Voici les étapes impliquées:
factorial (4) // 1er appel de fonction. Argument: 4 4 * factorial (3) // 2ème appel de fonction. Argument: 3 4 * (3 * factorial (2)) // 3e appel de fonction. Argument: 2 4 * (3 * (2 * factorial (1))) // 4ème appel de fonction. Argument: 1 4 * (3 * (2 * 1)) 24
Récursion de la queue de Kotlin
La récursivité de la queue est un concept générique plutôt que la fonctionnalité du langage Kotlin. Certains langages de programmation, dont Kotlin, l'utilisent pour optimiser les appels récursifs, alors que d'autres langages (par exemple Python) ne les prennent pas en charge.
Qu'est-ce que la récursivité de la queue?
Dans la récursivité normale, vous effectuez d'abord tous les appels récursifs et calculez enfin le résultat à partir des valeurs de retour (comme le montre l'exemple ci-dessus). Par conséquent, vous n'obtenez aucun résultat tant que tous les appels récursifs ne sont pas effectués.
Dans la récursivité de queue, les calculs sont effectués en premier, puis les appels récursifs sont exécutés (l'appel récursif transmet le résultat de votre étape actuelle à l'appel récursif suivant). Cela rend l'appel récursif équivalent à une boucle et évite le risque de débordement de pile.
Condition pour la récursion de la queue
Une fonction récursive est éligible pour la récursivité de queue si l'appel de fonction à elle-même est la dernière opération qu'elle effectue. Par exemple,
Exemple 1: non éligible pour la récursivité de queue car l'appel de la fonction à lui n*factorial(n-1)- même n'est pas la dernière opération.
fun factorial (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * factorial (n - 1)))
Exemple 2: éligible pour la récursivité de queue car l'appel de fonction à lui fibonacci(n-1, a+b, a)- même est la dernière opération.
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Pour dire au compilateur d'effectuer une récursion de queue dans Kotlin, vous devez marquer la fonction avec un tailrecmodificateur.
Exemple: récursivité de la queue
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) )
Lorsque vous exécutez le programme, la sortie sera:
354224848179261915075
Ce programme calcule le 100 e terme de la série de Fibonacci. Depuis, la sortie peut être un très grand entier, nous avons importé la classe BigInteger de la bibliothèque standard Java.
Ici, la fonction fibonacci()est marquée d'un tailrecmodificateur et la fonction est éligible pour l'appel récursif de queue. Par conséquent, le compilateur optimise la récursivité dans ce cas.
Si vous essayez de trouver le 20000 e terme (ou tout autre grand entier) de la série de Fibonacci sans utiliser la récursivité de queue, le compilateur lancera une java.lang.StackOverflowErrorexception. Cependant, notre programme ci-dessus fonctionne très bien. C'est parce que nous avons utilisé la récursivité de queue qui utilise une version basée sur une boucle efficace au lieu de la récursivité traditionnelle.
Exemple: factorielle utilisant la récursivité de la queue
L'exemple de calcul factoriel d'un nombre dans l'exemple ci-dessus (premier exemple) ne peut pas être optimisé pour la récursivité de queue. Voici un programme différent pour effectuer la même tâche.
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) )
Lorsque vous exécutez le programme, la sortie sera:
Factorielle de 5 = 120
Le compilateur peut optimiser la récursion dans ce programme car la fonction récursive est éligible pour la récursivité de queue, et nous avons utilisé un tailrecmodificateur qui indique au compilateur d'optimiser la récursivité.
