« Introduction générale à la programmation/Récursivité » : différence entre les versions
Contenu supprimé Contenu ajouté
m Robot : Remplacement de texte automatisé (- l'ordre + l’ordre , - t'as + t’as , - d'asile + d’asile , - d'argent + d’argent , - n'hésite + n’hesite , - m'y + m’y , - l'intervention + l’intervention , - "convention de nommage" +... |
m liens wp |
||
Ligne 6 :
| suivant = [[../Pointeurs/]]
}}
{{Wikipédia|Fonction récursive}}{{Wikipédia|Algorithme récursif}}
La récursivité est le phénomène de faire appel à soi même.
Dans la programmation, la récursivité est très utilisée, notamment dans les fonctions.
Ligne 18 :
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.
Ligne 39 :
Il s'agit là du prototype d'une fonction « récursive » : elle fait appel à elle-même (cinquième ligne). On peut chercher à comprendre ce qu'elle effectue comme calculs :
* si ''n'' est nul, elle renvoie ''a'' sans effectuer d'opérations ;
* si ''n'' est non
On voit facilement que cette fonction renvoie en fin de compte :
:''a + n + (n-1) + (n-2) + ··· + 3 + 2 + 1''
Ligne 50 :
Quelques exemples classiques de mise en œuvre de la récursivité :
* Calcul de ''n
* Résolution de [[w:Tour_de_Hanoï|la tour de Hanoï]].
* Vérification d’un [[w:Palindrome|palindrome]].
En outre, on peut aussi appeler une fonction depuis cette même fonction.
{{Bas de page
| |||