Une procédure ou une fonction peut contenir un appel à une autre procédure en son sein. Y compris, le sous-programme peut s'appeler. Dans ce cas, l'ordinateur s'en fiche. Il exécute également, comme toujours, systématiquement les commandes qu'il a rencontrées de haut en bas.
Si vous vous souvenez des mathématiques, vous pouvez y rencontrer le principe d'induction mathématique. C'est comme suit :
une affirmation est vraie pour chaque n naturel si
1. il est valable pour n = 1 et
2. de la validité de l'énoncé pour tout naturel arbitraire n = k il s'ensuit qu'il est vrai pour n = k+1.
En programmation, cette technique est appelée récursivité
La récursivité est un moyen de définir un ensemble d'objets en fonction de l'ensemble lui-même, sur la base de cas de base simples donnés.
Récursif sera également appelé une procédure (fonction) qui s'appelle elle-même directement ou via d'autres procédures et fonctions
Un exemple de procédure récursive :
vide Rec(int a)
{
si (a>0) Rec(a-1);
cout << un;
}
Schématiquement, le travail de récursivité peut être représenté par un organigramme
La procédure Rec() est exécutée avec le paramètre 3. Ensuite, à l'intérieur de la procédure avec le paramètre 3, la procédure avec le paramètre 2 est appelée, et ainsi de suite, jusqu'à ce que la procédure avec le paramètre 0 soit appelée. Lorsque la procédure avec le paramètre le paramètre 0 est appelé, l'appel récursif ne se produira déjà pas et la procédure avec le paramètre 0 imprimera le numéro 0 et se terminera. Ensuite, le contrôle est renvoyé à la procédure avec le paramètre 1, elle termine également son travail en imprimant le numéro 1, et ainsi de suite. avant la procédure avec le paramètre 3.
Toutes les procédures appelées sont stockées en mémoire jusqu'à ce qu'elles terminent leur travail. Le nombre de procédures concurrentes est appelé profondeur de récursivité.
|
Récursivité. Simulation de boucle
Nous avons vu que la récursivité est l'exécution répétée d'instructions contenues dans un sous-programme. Et cela, à son tour, est similaire au travail du cycle. Il existe des langages de programmation dans lesquels la construction de boucle est absente du tout, par exemple Prolog.
Essayons de simuler le travail de la boucle for.
La boucle for contient une variable de compteur de pas. Dans un sous-programme récursif, une telle variable peut être passée en paramètre.
// Procédure LoopImitation() avec deux paramètres.
// Premier paramètre – compteur de pas, second paramètre – nombre total d'étapes.
void LoopImitation(int i, int n)
{
cout << "Bonjour N" << je << fin ; // Opérateur à répéter pour toute valeur de i
if (i < n) // Jusqu'à ce que le compteur de boucle soit égal à n,
{ // appelle une nouvelle instance de la procédure, avec le paramètre i+1 (passe à la valeur suivante i).
BoucleImitation(i + 1, n);
}
}
|
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 |
entier Factoriel(int n)
{
si (n > 1)
return n * Factoriel(n - 1);
sinon retourner 1 ;
}
x = 1 ;
pour (i = 2; je <= n; i++)
x = x * je ;
cout << 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.
|
Tâche
Dans l'alphabet de la langue de la tribu "Tumba-Yumba" ; quatre lettres : "K", "L", "M" et "N". Vous devez afficher tous les mots composés de n lettres qui peuvent être construits à partir des lettres de cet alphabet.
Le problème est un problème normal de force brute qui peut être réduit à un problème plus petit.
Nous substituerons séquentiellement des lettres au mot.
La première position d'un mot peut être l'une des 4 lettres de l'alphabet (K. L, M, N).
Mettons la lettre K en premier. Ensuite, afin d'obtenir toutes les variantes avec la première lettre K, vous devez énumérer toutes les combinaisons possibles de lettres dans les positions n - 1 restantes et ainsi de suite. (voir photo).
 Ainsi, le problème se réduit à résoudre quatre problèmes de longueur n - 1.
Itérer sur n caractères de manière récursive
w[0]='K'; // itération sur les derniers L-1 caractères
w[0]='L'; // itération sur les derniers L-1 caractères
w[0]='M'; // itération sur les derniers L-1 caractères
w[0]='N'; // itération sur les derniers L-1 caractères
w - une chaîne de caractères qui stocke le mot de travail.
Ainsi, nous avons obtenu la récursivité. Nous pouvons organiser la solution du problème sous la forme d'une procédure récursive.
Reste à déterminer quand la récursivité prendra fin ? Lorsque tous les caractères sont définis, c'est-à-dire que le nombre de caractères définis est n. Dans ce cas, vous devez afficher le mot résultant à l'écran et quitter la procédure.
Le programme C++ ressemblera à ceci.
#include<iostream>
en utilisant l'espace de noms std ;
void TumbaWords( chaîne A, chaîne &w, int N )
// w - paramètre modifiable (string-result)
// La procédure TumbaWords reçoit l'alphabet sous forme de chaîne de caractères,
// le mot mot et le nombre de caractères déjà définis (précédant – 0).
{
int je ;
si (N == w.taille())
{
// si tous les caractères ont déjà été définis pour le mot,
// alors il faut sortir une chaîne et terminer la procédure
cout << w<< fin ;
retour;
}
pour ( je = 1; je < A.size(); je ++ )
{
// si la condition ci-dessus est fausse (c'est-à-dire que tous les caractères ne sont pas espacés,
// puis dans la boucle on parcourt tous les caractères de l'alphabet et
// place alternativement le caractère sur la première case libre
w[N] = A[i] ;
TumbaWords ( A, w, N+1 );
}
}
principal()
{
international ;
mot-clé ;
international ;
cin>> n;
word.resize(n); // augmente la chaîne à la taille n
TumbaWords( "KLMN", mot, 0 );
}
NOTEZ que w est un paramètre modifiable (chaîne de résultat) !
|