Nous allons voir le principe de fonctions récursives.
Pour le rappel concernant les fonctions: Fonctions. Une fonction est un sous-programme visant à réaliser une action donnée à travers l’exécution d’une série d’instructions. Une fonction exécute toujours une série d'instructions, et peut dans certains cas renvoyer un résultat (avec return).
Note: Si vous copier plusieurs fois le code dans une console web, vous pouvez avoir une erreur car une variable déclarée avec let avec le même nom a déjà été déclaré précédemment. Le plus simple est d'ouvrir une console web dans un autre onglet, ou d'enlever le let pour tester le code.
Voici plusieurs formulations de l'idée générale, illustréés par des exemples d'illustration juste après:
Une fonction récursive réutilise le résultat renvoyé (via return) et s'arrête quand on arrive au premier élément.
Une fonction récursive s'appelle elle-même sur le même problème de plus en plus petit et s'arrête quand elle a trouvé un problème pour lequel elle a une solution
Imaginons une fonction somme qui fait la somme des éléments de 1 à un certain nombre n.
Par exemple:
somme(10) sera égale à 10+9+8+7+6+5+4+3+2+1.
somme(9) sera égale à 9+8+7+6+5+4+3+2+1
somme(8) sera égale à 8+7+6+5+4+3+2+1
...
somme(2) sera égale à 2+1
somme(1) sera égale à 1
On peut s'apercevoir que :
somme(10) = 10+ somme(9)
or somme(9) = 9 + somme(8)
or somme(8) = 8 + somme(7)
...
or somme(2) = 2 + somme(1)
or somme(1) = 1
De manière générale, la fonction somme( ) peut s'écrire comme la fonction somme( ) du nombre précédent, et s'arrête quand on arrive à 1.
On pourrait donc écrire, pour resumer la fonction somme( ):
somme(n)= n + somme(n-1)
somme(1)=1
Imaginons une fonction palindrome qui vérifie si un mot est "symétrique". Par exemple, S0S est un palindrome: il peut se lire indépendamment dans sens et dans l'autre. C'est le cas des mots été, pop, kayak, ressasser, radar ... Pour cela on vérifie si la première et la dernière lettre sont semblables, puis la deuxième et l'avant dernière, puis la troisième avec l'avant-avant dernière jusqu'au milieu du mot. Partons du principe que lettre1==lettre2 revoie true si la lettre est identique et false sinon.
Par exemple:
palindrome("kayak") sera égale à ("k"=="k") + palindrome("aya") = true + palindrome("aya")
palindrome("aya") sera égale à ("a"=="a") + palindrome("y") = true + palindrome("y")
palindrome("y") sera égale à true
palindrome("selles") sera égale à ("s"=="s") + palindrome("elle") = true + palindrome("elle")
palindrome("elle") sera égale à ("e"=="e") + palindrome("ll") = true + palindrome("ll")
palindrome("ll") sera égale à ("l"=="l") + palindrome("") = true + palindrome("")
palindrome("") sera égale à true
palindrome("salles") sera égale à ("s"=="s") + palindrome("alle") = true + palindrome("alle")
palindrome("alle") sera égale à ("a"=="e") + palindrome("ll") = false + palindrome("ll")
palindrome("ll") sera égale à ("l"=="l") + palindrome("") = true + palindrome("")
palindrome("") sera égale à true
De manière générale, la fonction palindrome( ) d'un mot peut s'écrire comme la fonction palindrome( ) du mot moins la première et la dernière lettre , et s'arrête quand on arrive à 1 ou 0 lettres.
On pourrait donc écrire, pour resumer la fonction palindrome( ):
palindrome ( motEntier )= ( Première_Lettre_de_motEntier==Dernière_Lettre_de_motEntier) + palindrome(motEntier_Moins_La_Premiere_et_La_Dernière_Lettre)
palindrome("")= true et palindrome(UneSeuleLettre)=true
Pour définir une fonction itérative, on procède en deux étapes.
On doit définir quand la fonction récursive s'arrête, c'est à dire la "plus petite" solution au problème.
On doit définir comment la fonction se décompose, et fait appel à la même fonction sur un cas plus petit. La fonction récurive se propagera jusqu'à faire appel au cas de base.
La différence entre une fonction "habituelle" et une fonction récursive est dans la définition de la fonction. Dans une fonction récursive, on appelle la fonction dans sa définition (nom et arguments). Si vous vous rappelez, on rappelle la même fonction sur un "problème plus petit" comme défini dans le cas de propagation. On s'arrête quand on est dans le cas de base.
En lien avec le fait de s'arrêter quand on est dans le cas de base, dans une fonction récursive, on vérifie en premier lieu si on est dans le cas de base: dans ce cas on s'arrête et on retourne le résultat du cas de base.
Si on ne se trouve pas dans un cas de base, on retourne la formule de propagation. La formule de propagation contient forcément la fonction avec en attribut un problème plus petit.
function nomFonction( attributProbleme )
{
if (attributProblemeEstUnCasDeBase)
{
return solutionCasDeBase ;
}
else
{
return partieFormuleDePropagation + nomFonction(attributProblemePlusPetit);
}
Dans la suite, vous allez programmer étape par étape le premier exemple d'illustration en JavaScript (somme)
Vous allez ré-utiliser les exercices pour la fonction somme pour progammer des fonctions similaires
La fonction factorielle permet de mulitplier les nombre de 1 à un certain nombre n. Ainsi:
factorielle(1) vaut 1,
factorielle(2) vaut 2, soit 1*2
factorielle(3) vaut 6, soit 1*2*3
factorielle(4) vaut 24, soit 1*2*3*4
factorielle(5) vaut 120, soit 1*2*3*4*5
etc.
La fonction compteARebours permet d'afficher dans un alert les chiffre de n à 1 puis finit par afficher via alert "Zéééééééérrrrrrooooooo!!!!!"
compteARebours(0) affiche une fenêtre alert Zéééééééérrrrrrooooooo!!!!!
compteARebours(1) affiche une fenêtre alert 1, puis une fenêtre alert Zéééééééérrrrrrooooooo!!!!!
compteARebours(2) affiche une fenêtre alert 2, puis une fenêtre alert 1, puis une fenêtre alert Zéééééééérrrrrrooooooo!!!!!
compteARebours(3) affiche une fenêtre alert 3, puis une fenêtre alert 2, puis une fenêtre alert 1, puis une fenêtre alert Zéééééééérrrrrrooooooo!!!!!
compteARebours(52) affiche une fenêtre alert 52, puis une fenêtre alert 51, etc.. jusqu'à puis une fenêtre alert 1, puis une fenêtre alert Zéééééééérrrrrrooooooo!!!!!
La fonction compteurJusquA10 permet d'afficher dans un alert les chiffre de n à 10 puis finit par afficher via alert "Fin"
compteurJusquA10(0) affiche une fenêtre alert 0, puis une fenêtre alert 1, puis une fenêtre alert 2, puis une fenêtre alert 3, puis une fenêtre alert 4, puis une fenêtre alert 5, puis une fenêtre alert 6, puis une fenêtre alert 7, puis une fenêtre alert 8, puis une fenêtre alert 9, puis une fenêtre alert 10, puis une fenêtre alert Fin
compteurJusquA10(9) affiche une fenêtre alert 9, puis une fenêtre alert 10, puis une fenêtre alert Fin
Modifier la fonction compteurJusquA10 pour qu'elle fonctionne aussi si les nombre sont plus grand que 10
compteurJusquA10(12) affiche une fenêtre alert 12, puis une fenêtre alert 11, puis une fenêtre alert 10, puis une fenêtre alert Fin
compteurJusquA10(14) affiche une fenêtre alert 14, puis une fenêtre alert 13, puis une fenêtre alert 12, puis une fenêtre alert 11, puis une fenêtre alert 10, puis une fenêtre alert Fin
et toujours comme avant: compteurJusquA10(0) affiche une fenêtre alert 0, puis une fenêtre alert 1, puis une fenêtre alert 2, puis une fenêtre alert 3, puis une fenêtre alert 4, puis une fenêtre alert 5, puis une fenêtre alert 6, puis une fenêtre alert 7, puis une fenêtre alert 8, puis une fenêtre alert 9, puis une fenêtre alert 10, puis une fenêtre alert Fin
compteurJusquA10(9) affiche une fenêtre alert 9, puis une fenêtre alert 10, puis une fenêtre alert Fin
Dans la suite, vous allez programmer étape par étape le deuxième exemple d'illustration en JavaScript (palindrome)
Vous avez suivi le cours et les activités sur les fonctions récursives. Vous avez vu que:
les fonctions récursives s'appellent elle-mêmes sur un cas "plus simple"
les fonctions récursives présentent :
au moins un cas de base (celui pour lequel on connait directement le résultat) et
au moins un cas de propagation (le cas qui fait appel à la fonction elle-même jusqu'à arriver à un cas de base)
Quand on programme une fonction récursive, on programme ces cas de base et de propagation dans une condition.
Quand on programme, le cas de base renvoie le résultat et le cas de propragation fait appel à la même fonction dans la déclaration de la fonction. Utilise return dans les deux cas.