|
Dans la programmation informatique , la récursivité se produit quand une fonction ou une procédure - en d'autres termes , une séquence d' instructions pour effectuer une fonction particulière - se nomme , directement ou indirectement ? . La fonction ou une procédure modifie la valeur du paramètre (s) qui lui est passé pour la première fois , il est appelé et se qualifie avec la nouvelle valeur (s) . Factorielles
L'exemple classique de la récursivité des factorielles informatiques. Une factorielle est le produit d'un nombre entier positif donné, multipliée par tous les nombres entiers inférieurs . La factorielle de 5 est 5 * 4 * 3 * 2 * 1, la factorielle de 4 est 4 * 3 * 2 * 1 et ainsi de suite . La factorielle d'un nombre est égal à ce nombre multiplié par la factorielle du nombre immédiatement inférieur . En d'autres termes , factorielle ( 5) est le même que 5 * factorielle ( 4) , factorielle ( 4) est le même que 4 * factorielle ( 3) et ainsi de suite , donc une fonction factorielle simple pourrait être écrit comme :
int factorielle (int n) {return n * factorielle ( n - 1) ;}
cas de base
Le problème avec cette fonction simple, cependant , c'est qu'il n'a pas de scénario de base , ou une condition de lui dire quand arrêter . À l'heure actuelle , la fonction va continuer à se faire appeler lorsque n atteint zéro et au-delà dans les nombres négatifs , revenant factorielles absurdes . En réalité, une fonction factorielle doit cesser lorsque n = 1, donc une vraie fonction factorielle peut être écrite comme :
int factorielle (int n) {if ( n == 1) { return 1; } else {return n * factorielle ( n - 1 );}}
En anglais, la fonction examine le nombre qui lui est passé en paramètre, et , si le nombre est 1, renvoie 1. Sinon, la fonction retourne le nombre multiplié par la factorielle du nombre moins un.
Programme Stack
Tous les programmes récursifs doivent avoir un point bas , ou la base cas où l'opération est si trivial que la réponse peut être renvoyée directement . La récursivité fonctionne par l'addition, ou de poussée , et en supprimant , ou sauter, des trames individuelles à et à partir d'une structure de données appelée une pile de programme . Il ya seulement une quantité limitée d'espace sur la pile du programme , de sorte que , sans un scénario de base , un programme récursif serait tout simplement continue en cours d'exécution jusqu'à ce que la pile a débordé.
Pros
< br > récursivité est difficile à comprendre, car il n'est pas intuitive et peut apparaître , à première vue, d'impliquer logique circulaire ou faux. Selon IBM , la récursivité est rarement utilisé par les programmeurs des langages de programmation impératifs - qui ne précisent pas explicitement une séquence d'étapes à exécuter - parce qu'ils pensent qu'elle est lente et une perte d'espace . Toutefois, si elles sont appliquées correctement , la récursivité est une technique de programmation puissant qui peut simplifier certaines tâches de programmation.
|
