« Introduction générale à la programmation/Récursivité » : différence entre les versions
Contenu supprimé Contenu ajouté
Aucun résumé des modifications |
modification à mettre en forme, corriger les fautes.. |
||
Ligne 8 :
}}
La récursivité est le phénomène de faire appel à soi même.<br />
Dans la programmation, la récursivité est très utilisée, notamment dans les fonctions.
En effet, une fonction est une procédure qui retourne une valeur. Cette spécificité permet donc de créer une fonction qui s'appelle elle même en passant en paramètre le résultat du traitement effectué, et bien sur ce second appel pourra lui même appeller la fonction une troisième fois, et ainsi de suite.
On obtient donc un empilement d'appels, chacun réalisant une étape d'un traitement (souvent une manipulation de chaine de caractère).
Lorsqu'on arrive au bout du traitement, la dernière fonction fille appellée retourne une valeur qui se propagera jusqu'à la fonction mère par le même procédé. C'est de cette façon qu'une fonction récursive se termine.
Il est donc nécessaire de retenir deux points importants caractérisant la récursivité :
- la pile mémoire est abondamment utilisée par la récursivité (la plupart des erreurs de programmation récursive génèrent un dépassement de pile),
- une fonction récursive doit impérativement avoir une condition de fin qui provoquera le dépilement.
== Récursivité et fonctions ==
Quelques exemples classiques de mise en oeuvre de la récursivité :
- Résolution de la tour de hanoi.
- Vérification d'un palindrome.
En outre, on peut aussi appeler une fonction depuis cette même fonction.
| |||