La récursivité est un concept de programmation amusant mais peut être un peu difficile à apprendre. La récursivité signifie simplement quelque chose qui se répète. Si vous voulez voir un exemple effronté de récursivité, essayez de rechercher récursivité sur Google. Vous trouverez un œuf de Pâques où les suggestions de résultats de recherche sont récursives. Si, en revanche, vous souhaitez apprendre à coder une fonction récursive, lisez la suite !
Une fonction récursive est une fonction qui s'appelle elle-même. Vous créez essentiellement une boucle avec une fonction. Comme vous pouvez l'imaginer, ces fonctions peuvent être difficiles à écrire. Vous ne voulez pas que votre code s'exécute indéfiniment.
Semblable à une boucle, une fonction récursive sera contrôlée par une condition. Une fois la condition remplie, la fonction arrête de s'appeler, ce qui arrête la boucle. C'est ainsi que vous pouvez créer une fonction qui s'appelle sans qu'elle s'exécute indéfiniment.
Bien qu'une fonction récursive agisse comme une boucle, elle est exécutée différemment par l'ordinateur. Ainsi, certains algorithmes sont plus efficaces en boucle et d'autres bénéficient d'une fonction récursive. Mais avant de voir comment utiliser une fonction récursive, vous devez savoir comment en écrire une.
Toutes les fonctions récursives ont la même structure de base :
nom de la FONCTION
SI condition ALORS
RETOUR résultat
AUTRE
Nom de la fonction d'appel
FIN DE FONCTION L'exemple ci-dessus est écrit en pseudo-code. Il décrit la structure de la fonction, qui peut être appliquée à n'importe quel langage. Pour plus de simplicité, dans cet article, nous nous concentrerons sur Python.
La première chose à noter à propos d'une fonction récursive est que lorsque la condition est remplie, la fonction sort de la récursivité. Cela signifie que lorsque vous écrivez une fonction récursive, la première chose que vous voudrez déterminer est quand arrêter la récursivité.
Si la condition n'est pas remplie, la fonction s'appellera. Ainsi, si vous souhaitez envoyer des informations à la boucle suivante, vous devrez les envoyer en tant qu'argument dans votre fonction. Cela peut donner beaucoup plus de puissance aux fonctions récursives.
Il sera beaucoup plus facile de comprendre comment fonctionne la récursivité lorsque vous la verrez en action. Pour le démontrer, écrivons une fonction récursive qui renvoie la factorielle d'un nombre.
Les factorielles renvoient le produit d'un nombre et de tous les entiers qui le précèdent. Par exemple, la factorielle de 5 est 5 x 4 x 3 x 2 x 1 ou 120.
def factorialFunction(numberToMultiply) :
si nombreAMultiplier ==1 :
retour 1
autre :
renvoie nombreVersMultiplier * Fonctionfactorielle(nombreVersMultiplier - 1)
résultat =fonctionfactorielle(3)
imprimer (résultat)
//Sorties :6
Le programme ci-dessus vous donnera le résultat 6, qui est la factorielle du nombre 3. Cela peut être un peu déroutant au début. Cela nous aidera si nous parcourons le programme étape par étape.
La récursivité est un concept délicat. Il peut être utile de le considérer comme empilant une fonction au-dessus d'une autre fonction. Une fois qu'une fonction est finalement résolue, elle peut renvoyer les informations dans la pile, jusqu'à ce que toutes les fonctions aient leur réponse.
C'est en fait à peu près ce que fait votre ordinateur. Lorsque vous appelez la fonction, elle est conservée en mémoire jusqu'à ce qu'elle soit renvoyée. Cela signifie que les fonctions récursives peuvent utiliser beaucoup plus de mémoire qu'une boucle.
Ainsi, il n'est peut-être pas efficace d'écrire des boucles sous forme de fonctions récursives, mais c'est un excellent moyen de s'entraîner à les construire. Vous devriez pouvoir coder des boucles en tant que fonctions récursives avec des résultats similaires.
print("Entrez un nombre pair :")
je =int(entrée())
tandis que (i % 2) !=0 :
print("Ce nombre n'est pas pair. Veuillez entrer un nouveau nombre :")
je =int(input()) Cette boucle peut également être écrite de manière récursive comme :
def recursiveFunction(number) :
si (nombre % 2) ==0 :
numéro de retour
autre:
print("Ce nombre n'est pas pair. Veuillez entrer un nouveau nombre :")
fonction récursive(int(input()))
print("Entrez un nombre pair :")
i =recursiveFunction(int(input())) La première étape consiste à déterminer quand vous voulez que votre fonction s'arrête. Dans ce cas, nous voulons qu'il s'arrête une fois qu'un nombre pair est entré. Dans notre exemple, nombre suit l'entrée de l'utilisateur. S'ils saisissent un nombre pair, nous renvoyons le nombre. Sinon, nous continuerons à demander un nouveau numéro.
Pour configurer la boucle, nous appelons à nouveau notre fonction. Mais cette fois, le numéro que nous passons à la fonction suivante est le nouveau numéro saisi par l'utilisateur. Le prochain appel de fonction vérifiera le numéro.
C'est vraiment une mauvaise fonction ! Oui, il vérifie si le nombre est pair, comme notre boucle, mais ce n'est pas efficace. Chaque fois que l'utilisateur entre un nombre impair, la fonction est maintenue en mémoire et une nouvelle fonction est appelée. Si vous le faites suffisamment de fois, vous manquerez de mémoire !
Les exemples ci-dessus étaient de bons exemples de quand ne pas utiliser la récursivité. Alors, où la récursivité est-elle utilisée ? Un bon exemple de cas où vous voudriez utiliser la récursivité est la recherche d'un arbre binaire.
Lorsque les données sont structurées dans un arbre binaire, vous devez emprunter de nombreux chemins pour rechercher des données. A chaque point de l'arborescence, vous devez décider si vous souhaitez poursuivre la recherche à droite ou à gauche. Vous pouvez enregistrer la partie de l'arbre que vous avez visitée dans une variable, mais une fonction récursive peut naturellement suivre cette information.
Imaginez que nous recherchions le nombre six dans l'arbre ci-dessus. Nous pourrions faire une fonction récursive qui recherche l'arbre de gauche à droite. L'algorithme ressemblerait à ceci :
FONCTION searchTree(branchToSearch)
SI trouve 6 OU fin de l'arbre ALORS
RETOUR résultat
AUTRE
Branche PROCESSUS
CALL FUNCTION searchTree (gauche)
CALL FUNCTION searchTree (droite)
FIN DE FONCTION Dans cet exemple de pseudo-code, l'algorithme rechercherait d'abord le côté gauche de l'arbre. Chaque fois qu'il visite un nouveau numéro, la fonction est mise en pause et conservée en mémoire. Cela nous permet de suivre où nous avons été.
L'algorithme recherchera toujours le côté gauche aussi loin que possible en premier. une fois qu'il atteint la fin de l'arbre, le searchTree (gauche) se terminera et il vérifiera le côté droit. Une fois les deux côtés cochés, la recherche sauvegarde une branche et continue à vérifier le côté droit.
Si les algorithmes cherchaient dans tout l'arbre, ils le feraient dans l'ordre :
2, 7, 2, 6, 5, 11, 5, 9 et 4
Voyez si vous pouvez suivre en utilisant le pseudo-code ci-dessus.
La récursivité est un sujet avancé. Il faudra un certain temps pour comprendre et encore plus pour devenir bon à le coder. Cela vous aidera si vous parcourez les fonctions récursives étape par étape. Il peut même être utile d'empiler des fiches ou des post-it au fur et à mesure que vous parcourez une fonction lorsque vous apprenez à représenter chaque appel de fonction.
Lorsque vous écrivez une fonction récursive, commencez par décider comment vous voulez quitter la fonction. Ensuite, déterminez comment configurer votre boucle. Identifiez les informations qui doivent être envoyées au prochain appel de fonction et celles qui doivent être renvoyées.
La meilleure façon d'apprendre la récursivité est de la pratiquer et d'apprendre de vos erreurs. Regardez une partie de votre ancien code et mettez-vous au défi de réécrire les boucles en tant que fonctions récursives. Cela ne rendra probablement pas votre code plus efficace, mais ce sera une bonne pratique.