Récursivité
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 n = k naturel arbitraire, 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 termes d'ensemble lui-même, en fonction de données cas de base simples.
Récursif est une procédure (fonction) qui s'appelle elle-même directement ou via d'autres procédures et fonctions.
Exemple
def Rec(a) :
si (a>0) : Rec(a-1)
imprimer(a)
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 0 est appelée, l'appel récursif ne se produira plus et la procédure avec le paramètre 0 imprimera le numéro 0 et sortira. 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é.
|
La récursivité comme remplacement 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 totalement absente. 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
def LoopImitation(i, n):
print("Hello N", i) # Instruction à répéter pour toute valeur de i
si je < n : # jusqu'à ce que le compteur de boucle soit égal à la valeur n,
LoopImitation(i + 1, n) # appelle une nouvelle instance de la procédure,
# avec le paramètre i+1 (aller à la valeur suivante i)
|
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.
| Fonction factorielle récursive |
Algorithme itératif |
def Factoriel(n):
si n > 1:
retour n * Factoriel(n - 1)
autre:
retour 1
x=1
pour i dans la plage (1, n + 1):
x = x * je ;
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". Il est nécessaire d'afficher à l'écran tous les mots composés de n lettres pouvant ê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).
Tout d'abord, mettez 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 le n-1 positions et .etc. (voir l'image)
Ainsi, nous avons trouvé une solution récursive : dans une boucle, parcourir toutes les premières lettres possibles (en mettant tour à tour chaque lettre de l'alphabet en premier) et pour chaque cas construire toutes les "queues" possibles ; longueur n-1.
Itération récursive de caractères
Vous devez arrêter la récursivité et sortir le mot fini lorsque la partie restante est vide (n = 0), c'est-à-dire toutes les lettres sont déjà sélectionnées.
La procédure récursive ressemblerait à ceci :
def TumbaWords(mot, alphabet, n):
si n < 1:
imprimer (mot)
retour
pour c dans l'alphabet :
TumbaMots(mot+c, alphabet, n - 1)
|