Qu’est-ce que la récursivité et comment l’utilisez-vous?

Hibou Gourou

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 la récursivité sur Google. Vous trouverez un œuf de Pâques où les suggestions de résultats de recherche sont récursives. Si, au contraire, vous souhaitez apprendre à coder une fonction récursive, lisez la suite!

Qu'est-ce qu'une fonction récursive?

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 délicates à é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 cesse de s'appeler, ce qui arrête la boucle. C'est ainsi que vous pouvez créer une fonction qui s'appelle elle-même sans qu'elle ne 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 dans une 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.

Comment écrire une fonction récursive

Toutes les fonctions récursives ont la même structure de base:

 FUNCTION name
 IF condition THEN
 RETURN result
 ELSE
 CALL FUNCTION name
 END FUNCTION

L'exemple ci-dessus est écrit en pseudo-code. Il décrit la structure de la fonction, qui peut être appliquée à n'importe quelle langue. 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 quitte 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 elle-même. Donc, si vous voulez envoyer des informations à la boucle suivante, vous devrez les envoyer comme argument dans votre fonction. Cela peut donner aux fonctions récursives beaucoup plus de puissance.

En relation: Qu'est-ce qu'une fonction dans la programmation?

Exemple de fonction récursive en Python

Il sera beaucoup plus facile de comprendre le fonctionnement de 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 avant lui. Par exemple, la factorielle de 5 est 5 x 4 x 3 x 2 x 1 ou 120.

 def factorialFunction(numberToMultiply):
 if numberToMultiply == 1 :
 return 1
 else :
 return numberToMultiply * factorialFunction(numberToMultiply - 1)

 result = factorialFunction(3)
 print(result)
 //Outputs: 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 aidera si nous exécutons le programme étape par étape.

  1. Lorsque la fonction est appelée, numberToMultiply vaut 3.
  2. La condition n'est pas remplie, nous passons donc à la condition else .
  3. Notre fonction renvoie 3 * mais est ensuite mise en pause. Il doit s'appeler pour déterminer le reste de la valeur qu'il renvoie.
  4. Lorsque la fonction est appelée cette fois, la valeur de numberToMultiply est égale à 2.
  5. La condition n'est pas remplie, nous passons donc à la condition else.
  6. Notre fonction renvoie 2 * mais est ensuite mise en pause. Il doit s'appeler pour déterminer le reste de la valeur qu'il renvoie.
  7. La fonction est appelée à nouveau. Cette fois, la valeur de numberToMultiply est égale à 1.
  8. Notre condition si est remplie. La fonction renvoie 1.
  9. La fonction de l'étape 6 peut maintenant ramener 2 * 1 à la fonction de l'étape 3.
  10. La fonction de l'étape trois peut maintenant renvoyer 3 * 2 * 1, soit 6.

La récursivité est un concept délicat. Il peut être utile de considérer cela comme l'empilement d'une fonction sur 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 comme des fonctions récursives, mais c'est un excellent moyen de s'entraîner à les construire. Vous devriez être capable de coder des boucles en tant que fonctions récursives avec des résultats similaires.

Un exemple de conversion d'une boucle en fonction récursive

 print("Enter an even number:")
 i = int(input())
 while (i % 2) != 0 :
 print("That number is not even. Please enter a new number:")
 i = int(input())

Cette boucle peut également être écrite de manière récursive comme:

 def recursiveFunction(number) :
 if (number % 2) == 0 :
 return number
 else:
 print("That number is not even. Please enter a new number:")
 recursiveFunction(int(input()))

 print("Enter and even number:")
 i = recursiveFunction(int(input()))

La première étape consiste à déterminer quand vous souhaitez 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 entrent un nombre pair, nous retournons 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 entré par l'utilisateur. Le prochain appel de fonction vérifiera le numéro.

C'est une très 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 conservée en mémoire et une nouvelle fonction est appelée. Si vous faites cela suffisamment de fois, vous manquerez de mémoire!

Connexes: Exemples Python de base qui vous aideront à apprendre rapidement

Un exemple réel d'une fonction récursive

Les exemples ci-dessus étaient de bons exemples de cas où 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 dans 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 continuer 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 ces informations.

Imaginez que nous recherchons le numéro six dans l'arbre ci-dessus. Nous pourrions créer une fonction récursive qui recherche l'arbre de gauche à droite. L'algorithme ressemblerait à ceci:

 FUNCTION searchTree(branchToSearch)
 IF find 6 OR end of tree THEN
 RETURN result
 ELSE
 PROCESS branch
 CALL FUNCTION searchTree(left)
 CALL FUNCTION searchTree(right)
 END FUNCTION

Dans cet exemple de pseudocode, l'algorithme rechercherait d'abord le côté gauche de l'arbre. Chaque fois qu'elle 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 cherchera 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 que les deux côtés sont vérifiés, la recherche sauvegarde une branche et continue de vérifier le côté droit.

Si les algorithmes recherchaient 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.

Avis sur la récursivité

La récursivité est un sujet avancé. Il faudra un certain temps pour comprendre et même plus longtemps pour bien 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.

Lors de l'écriture d'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 certains de vos anciens codes 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.