Please enable JavaScript.
Coggle requires JavaScript to display documents.
La notion de récursivité - Coggle Diagram
La notion de récursivité
remarque
Attention ! L’existence d’une condition d’arrêt ne signifie pas que l’appel récursif s’arrête grâce à celle-ci.
-
appel(-1) conduit par appel récursif à l'exécution de appel(-2),
appel(-2) conduit par appel récursif à l'exécution de appel(-3),
appel(-3) conduit par appel récursif à l'exécution de appel(-4),
-
-
-
-
-
-
Dans toute fonction récursive, il est nécessaire d'avoir une condition d'arrêt ; on parle aussi de condition de terminaison.
bilan
-
Une fonction récursive à besoin de la présence d'une condition d'arrêt sinon la fonction ne peut pas s'appeler elle-même.
il faut faire attention que la condition d’arrêt soit atteinte après un nombre fini d’appels.
Cette condition d'arrêt ne peut en aucun cas être un appel récursif.
il est pertinent de choisir une condition d'arrêt correspondant à un "cas simple" pour lequel vous connaissez la valeur à renvoyer.
si on recherche l’efficacité (une exécution rapide) et si le programme peut être écrit sans trop de difficultés en itératif, on préférera l’itératif.
on préfére la récursivité surtout dans les situations où la solution itérative est difficile à obtenir:
EXEMPLE & EXERCICE
-
-
La récursivité ajoute de la simplicité (de la compacité) lors de l'écriture de code, ce qui facilite le débogage,
-
propriétés
Pour s'assurer de la terminaison d'un algorithme récursif, il suffit d'identifier une suite strictement décroissante d'entiers positifs ou nuls.
-
-
-
L'identification d'une séquence strictement décroissante d'entiers positifs ou nuls peut prouver que l'algorithme récursif se termine par un nombre limité d'appels. Si la séquence commence à partir de n, il y aura au plus n appels récursifs
