3.16. Types de données : récursion
Page 19 | Écouter en audio
3.16. Types de données : récursivité
La récursion est un concept fondamental en informatique et un sujet essentiel en programmation logique. Il fait référence à la technique consistant à faire en sorte qu'un programme s'appelle lui-même dans le cadre de son exécution. Cela peut être extrêmement utile pour résoudre des problèmes qui peuvent être décomposés en problèmes plus petits de même nature.
La récursion est une alternative à l'utilisation de boucles pour répéter des actions. Plutôt que de définir une boucle qui s'exécute jusqu'à ce qu'une certaine condition soit remplie, une fonction récursive s'exécute jusqu'à ce qu'un cas de base soit rempli.
Qu'est-ce que la récursivité ?
La récursion est une méthode de résolution de problèmes dans laquelle la solution à un problème particulier est basée sur la résolution d'instances plus petites du même problème. Un exemple classique de problème pouvant être résolu par récursion est le calcul de la factorielle d’un nombre. La factorielle d'un nombre n est le produit de tous les entiers positifs inférieurs ou égaux à n. Ceci peut être résolu en utilisant la récursion, car la factorielle de n (représentée par n !) peut être exprimée par n * (n-1) !.
Comment fonctionne la récursivité ?
Lorsqu'une fonction est appelée dans un programme, le système alloue un bloc de mémoire pour stocker les valeurs des variables et les adresses de retour de la fonction. Lorsqu'une fonction est appelée, un nouveau bloc mémoire est alloué en plus du bloc mémoire précédent. Ce processus se poursuit jusqu'à ce que la condition de fin soit remplie, auquel cas la fonction cesse de s'appeler. Ensuite, le système commence à désallouer les blocs de mémoire, en commençant par le bloc de mémoire le plus récent et en remontant au bloc de mémoire d'origine.
Exemple de récursion
Un exemple courant de récursion est la séquence de Fibonacci, où chaque nombre est la somme des deux nombres précédents. La séquence commence par 0 et 1. Les nombres suivants sont obtenus en additionnant les deux nombres précédents pour obtenir le nombre suivant. La séquence ressemble à ceci : 0, 1, 1, 2, 3, 5, 8, 13, 21, et ainsi de suite. Cela peut être facilement programmé en utilisant la récursion.
Dans la fonction ci-dessus, la condition de terminaison est lorsque n est égal ou inférieur à 1. Dans ce cas, la fonction renvoie n. Sinon, la fonction est appelée deux fois, une fois avec n-1 et une fois avec n-2, et renvoie la somme de ces deux valeurs.
Avantages et inconvénients de la récursion
La récursion peut rendre le code plus propre et plus facile à comprendre. Des problèmes complexes qui seraient difficiles à résoudre à l'aide de boucles peuvent être facilement résolus à l'aide de la récursivité.
Cependant, la récursivité a aussi ses inconvénients. Cela peut conduire à une utilisation inefficace de la mémoire, car chaque appel de fonction nécessite un bloc de mémoire distinct. En outre, la récursivité peut entraîner un ralentissement des performances, car l'allocation et la désallocation de mémoire prennent du temps. De plus, si la condition de terminaison n'est pas remplie, la fonction continuera à s'appeler indéfiniment, entraînant une erreur de débordement de pile.
En résumé, la récursivité est un outil puissant en programmation logique, mais elle doit être utilisée avec précaution. Il est important de comprendre comment fonctionne la récursivité et quels sont ses avantages et ses inconvénients avant de décider de l'utiliser.
Répondez maintenant à l’exercice sur le contenu :
Qu’est-ce que la récursivité en informatique et comment ça marche ?
Tu as raison! Félicitations, passez maintenant à la page suivante
Vous avez raté! Essayer à nouveau.
Page suivante de lebook gratuit :
20Variables et constantes
3 minutes
Obtenez votre certificat pour ce cours gratuitement ! en téléchargeant lapplication Cursa et en lisant lebook qui sy trouve. Disponible sur Google Play ou App Store !
