Récursivité et itération
Pour comprendre la récursivité, vous devez comprendre la récursivité...
Itération en programmation -
une étaped'un processus de traitement de données cyclique.
Souvent, les algorithmes itératifs à l'étape en cours (itération) utilisent le résultat de la même opération ou action calculée aux étapes précédentes. Un exemple de tels calculs est le calcul des relations de récurrence.
Un exemple simple de valeur récursive est la factorielle :
\(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
Le calcul de la valeur à chaque étape (itération) est
\(N=N \cdot i\) . Lors du calcul de la valeur de
\(N\), nous prenons la valeur déjà stockée
\(N\).< br />
La factorielle d'un nombre peut également être décrite à l'aide de la
formule récurrente :
\(\begin{equation*} n != \begin{cases} 1 &\text{n <= 1,}\\ (n-1) ! \cdot n &\text{n > 1.} \end{cas} \end{équation*}\)
Vous remarquerez peut-être que cette description n'est rien de plus qu'une fonction récursive.
Ici, la première ligne (
\(n <= 1\)) est le cas de base (condition de terminaison de la récursivité) et la deuxième ligne est la transition vers l'étape suivante. < br />
| Fonction factorielle récursive |
Algorithme itératif |
static int Factoriel(int n){
si (n > 1)
return n * Factoriel(n - 1);
sinon retourner 1 ;
}
int x = 1 ;
pour (int je = 2; je <= n; je++)
x = x * je ;
Console.WriteLine("%d", x);
Il faut comprendre que les appels de fonction impliquent une surcharge supplémentaire, donc un calcul factoriel non récursif sera légèrement plus rapide.
Conclusion : où vous pouvez écrire un programme avec un algorithme itératif simple, sans récursivité, alors vous devez écrire sans récursivité. Mais encore, il existe une grande classe de problèmes où le processus de calcul est mis en œuvre uniquement par récursivité.
En revanche, les algorithmes récursifs sont souvent plus compréhensibles.