Bonjour Habrahabr!

Dans cet article, nous parlerons des problèmes de récursivité et de la manière de les résoudre.

En bref sur la récursivité

La récursivité est un phénomène assez courant qui se produit non seulement dans le domaine scientifique, mais aussi dans Vie courante. Par exemple, l'effet Droste, le triangle de Sierpinski, etc. Une façon de voir la récursion est de pointer la caméra Web vers l'écran de l'ordinateur, bien sûr, après l'avoir d'abord allumée. Ainsi, la caméra enregistrera l'image de l'écran de l'ordinateur et l'affichera sur cet écran, ce sera quelque chose comme une boucle fermée. En conséquence, nous observerons quelque chose de similaire à un tunnel.

En programmation, la récursivité est étroitement liée aux fonctions, plus précisément, c'est grâce aux fonctions en programmation qu'il existe une récursivité ou une fonction récursive. En mots simples, la récursivité est la définition d'une partie d'une fonction (méthode) à travers elle-même, c'est-à-dire qu'il s'agit d'une fonction qui s'appelle, directement (dans son corps) ou indirectement (à travers une autre fonction).

On a beaucoup parlé de la récursivité. Voici quelques bonnes ressources :

• Récursion et problèmes récursifs. Domaines d'application de la récursivité

On suppose que le lecteur est théoriquement familier avec la récursivité et sait de quoi il s'agit. Dans cet article, nous accorderons plus d’attention aux problèmes de récursivité.

Tâches

Lors de l’apprentissage de la récursion, le moyen le plus efficace de comprendre la récursion est de résoudre des problèmes.

Comment résoudre les problèmes de récursion ?

Tout d’abord, vous devez comprendre que la récursivité est une sorte d’exagération. D’une manière générale, tout ce qui est résolu de manière itérative peut être résolu de manière récursive, c’est-à-dire en utilisant une fonction récursive.

du réseau

Tout algorithme implémenté sous forme récursive peut être réécrit sous forme itérative et vice versa. La question reste de savoir si cela est nécessaire et quelle sera son efficacité.

Les arguments suivants peuvent être avancés pour justifier cela.

Pour commencer, rappelons les définitions de la récursivité et de l’itération. La récursivité est une manière d'organiser le traitement des données dans laquelle un programme s'appelle directement ou avec l'aide d'autres programmes. L'itération est une manière d'organiser le traitement des données dans laquelle certaines actions sont répétées plusieurs fois sans conduire à des appels de programme récursifs.

Après quoi on peut conclure qu’ils sont mutuellement interchangeables, mais pas toujours avec les mêmes coûts en termes de ressources et de rapidité. Pour justifier cela, nous pouvons donner l'exemple suivant : il existe une fonction dans laquelle, afin d'organiser un certain algorithme, il y a une boucle qui effectue une séquence d'actions en fonction de la valeur actuelle du compteur (cela peut ne pas dépendre de il). Puisqu’il existe un cycle, cela signifie que le corps répète une séquence d’actions – des itérations du cycle. Vous pouvez déplacer les opérations dans un sous-programme distinct et lui transmettre la valeur du compteur, le cas échéant. A la fin de l'exécution du sous-programme, on vérifie les conditions d'exécution de la boucle, et si c'est vrai, on procède à un nouvel appel au sous-programme ; si c'est faux, on termine l'exécution. Parce que Nous avons placé tout le contenu de la boucle dans un sous-programme, ce qui signifie que la condition d'exécution de la boucle est également placée dans le sous-programme, et elle peut être obtenue via la valeur de retour de la fonction, les paramètres passés par référence ou le pointeur vers le sous-programme , ainsi que des variables globales. De plus, il est facile de montrer qu'un appel à un sous-programme donné depuis une boucle peut être facilement converti en un appel ou un non-appel (renvoyant une valeur ou simplement complétant un travail) d'un sous-programme depuis lui-même, guidé par certaines conditions (celles qui étaient auparavant dans l'état de boucle). Maintenant, si vous regardez notre programme abstrait, cela ressemble à peu près à transmettre des valeurs à un sous-programme et à les utiliser, que le sous-programme modifiera une fois terminé, c'est-à-dire nous avons remplacé la boucle itérative par un appel récursif à un sous-programme pour résoudre un algorithme donné.

La tâche consistant à amener la récursion dans une approche itérative est symétrique.

En résumé, nous pouvons exprimer les réflexions suivantes : pour chaque approche, il existe sa propre classe de tâches, qui est déterminée par les exigences spécifiques d'une tâche spécifique.

Vous pouvez en savoir plus à ce sujet

Tout comme une énumération (cycle), la récursivité doit avoir une condition d'arrêt - Cas de base (sinon, tout comme un cycle, la récursivité fonctionnera pour toujours - infinie). Cette condition est le cas auquel va la récursion (étape de récursion). À chaque étape, une fonction récursive est appelée jusqu'à ce que l'appel suivant déclenche la condition de base et que la récursion s'arrête (ou plutôt revienne au dernier appel de fonction). Toute la solution consiste à résoudre le cas de base. Dans le cas où une fonction récursive est appelée pour résoudre tâche difficile(pas le cas de base), un certain nombre d'appels ou d'étapes récursifs sont effectués afin de réduire le problème à un problème plus simple. Et ainsi de suite jusqu'à ce que nous obtenions Solution basique.

La fonction récursive consiste donc à

• Condition d'arrêt ou cas de base
• Une condition de continuation ou une étape de récursion est un moyen de réduire un problème à des problèmes plus simples.

Regardons cela en utilisant l'exemple de la recherche de la factorielle :

Solution de classe publique ( public static int recursion(int n) ( // condition de sortie // Cas de base // quand arrêter de répéter la récursion ? if (n == 1) ( return 1; ) // Étape de récursion / retour de condition récursive recursion( n - 1) * n; ) public static void main(String args) ( System.out.println(recursion(5)); // appelle la fonction récursive ) )

Ici, la condition de base est la condition lorsque n=1. Puisque nous savons que 1!=1 et que pour calculer 1! nous n'avons besoin de rien. Pour calculer 2 ! nous pouvons utiliser 1 !, c'est-à-dire 2!=1!*2. Pour en calculer 3 ! il nous faut 2!*3... Pour calculer n! nous avons besoin de (n-1)!*n. C'est l'étape de récursion. Autrement dit, pour obtenir la valeur factorielle d’un nombre n, il suffit de multiplier la valeur factorielle du nombre précédent par n.

Mots clés:

• récursivité
• Tâches
• Java

Ajouter des balises

La récursivité, c'est lorsqu'un sous-programme s'appelle. Lorsqu'ils sont confrontés pour la première fois à une telle construction algorithmique, la plupart des gens rencontrent certaines difficultés, mais avec un peu de pratique, la récursivité deviendra claire et très claire. outil utile dans votre arsenal de programmation.

1. L'essence de la récursion

Une procédure ou une fonction peut contenir des appels à d'autres procédures ou fonctions. La procédure peut également s'appeler elle-même. Il n'y a pas de paradoxe ici : l'ordinateur n'exécute que séquentiellement les commandes qu'il rencontre dans le programme et, s'il rencontre un appel de procédure, il commence simplement à exécuter cette procédure. Peu importe la procédure qui a donné l'ordre de le faire.

Exemple de procédure récursive :

Procédure Rec(a : entier) ; commencer si un>

Considérons ce qui se passe si un appel, par exemple, de la forme Rec(3) est effectué dans le programme principal. Vous trouverez ci-dessous un organigramme montrant la séquence d'exécution des instructions.

Riz. 1. Schéma fonctionnel de la procédure récursive.

La procédure Rec est appelée avec le paramètre a = 3. Elle contient un appel à la procédure Rec avec le paramètre a = 2. L'appel précédent n'est pas encore terminé, vous pouvez donc imaginer qu'une autre procédure est créée et que la première ne termine son travail que lorsque ça se termine. Le processus appelant se termine lorsque le paramètre a = 0. A ce stade, 4 instances de la procédure sont exécutées simultanément. Le nombre de procédures effectuées simultanément est appelé profondeur de récursion.

La quatrième procédure appelée (Rec(0)) imprimera le nombre 0 et terminera son travail. Après cela, le contrôle revient à la procédure qui l'a appelé (Rec(1)) et le numéro 1 est imprimé. Et ainsi de suite jusqu'à ce que toutes les procédures soient terminées. L'appel d'origine imprimera quatre chiffres : 0, 1, 2, 3.

Une autre image visuelle de ce qui se passe est présentée sur la Fig. 2.

Riz. 2. L'exécution de la procédure Rec avec le paramètre 3 consiste à exécuter la procédure Rec avec le paramètre 2 et à imprimer le numéro 3. À son tour, l'exécution de la procédure Rec avec le paramètre 2 consiste à exécuter la procédure Rec avec le paramètre 1 et à imprimer le numéro 2. Etc. .

Comme exercice personnel, réfléchissez à ce qui se passe lorsque vous appelez Rec(4). Considérez également ce qui se passerait si vous appeliez la procédure Rec2(4) ci-dessous, avec les opérateurs inversés.

Procédure Rec2(a : entier) ; commencer à écrire(a); si a>0 alors Rec2(a-1); fin;

Veuillez noter que dans les exemples ci-dessus, l'appel récursif est à l'intérieur opérateur conditionnel. Ce condition nécessaire pour que la récursion se termine un jour. Notez également que la procédure s'appelle avec un paramètre différent de celui avec lequel elle a été appelée. Si la procédure n'utilise pas de variables globales, cela est également nécessaire pour que la récursion ne se poursuive pas indéfiniment.

Un peu plus possible circuit complexe: La fonction A appelle la fonction B, qui à son tour appelle A. C'est ce qu'on appelle récursivité complexe. Il s'avère que la procédure décrite en premier doit appeler une procédure qui n'a pas encore été décrite. Pour que cela soit possible, vous devez utiliser .

Procédure A(n : entier) ; (Description avant (en-tête) de la première procédure) procédure B(n : entier) ; (Description avancée de la deuxième procédure) procédure A(n : entier) ; ( Description complète les procédures A) commencent writeln(n); B(n-1); fin; procédure B(n : entier) ; (Description complète de la procédure B) start writeln(n); si n

Une déclaration anticipée de procédure B permet de l'appeler depuis une procédure A. Une déclaration anticipée de procédure A dans dans cet exemple non requis et ajouté pour des raisons esthétiques.

Si la récursion ordinaire peut être comparée à un ouroboros (Fig. 3), alors l'image d'une récursion complexe peut être tirée du célèbre poème pour enfants, où « Les loups avaient peur et se mangeaient les uns les autres ». Imaginez deux loups se dévorant et vous comprendrez la récursion complexe.

Riz. 3. Ouroboros – un serpent dévorant sa propre queue. Tiré du traité alchimique « Synosius » de Théodore Pelecanos (1478).

Riz. 4. Récursion complexe.

3. Simuler une boucle par récursivité

Si une procédure s’appelle elle-même, elle provoque essentiellement la réexécution des instructions qu’elle contient, à la manière d’une boucle. Certains langages de programmation ne contiennent pas du tout de constructions en boucle, laissant les programmeurs organiser les répétitions en utilisant la récursion (par exemple, Prolog, où la récursion est une technique de programmation de base).

Par exemple, simulons le travail pour la boucle. Pour ce faire, nous avons besoin d'une variable de compteur de pas, qui peut être implémentée, par exemple, en tant que paramètre de procédure.

Exemple 1.

Procédure LoopImitation(i, n : entier); (Le premier paramètre est le compteur de pas, le deuxième paramètre est le nombre total de pas) start writeln("Hello N ", i); //Voici les instructions qui seront répétées si je

Le résultat d'un appel de la forme LoopImitation(1, 10) sera l'exécution d'instructions dix fois, faisant passer le compteur de 1 à 10. Dans ce cas, ce qui suit sera imprimé :

Bonjour N1
Bonjour N°2
…
Bonjour N10

En général, il n'est pas difficile de voir que les paramètres de la procédure constituent les limites de modification des valeurs du compteur.

Vous pouvez échanger l'appel récursif et les instructions à répéter, comme dans l'exemple suivant.

Exemple 2.

Procédure LoopImitation2(i, n : entier); commencer si je

Dans ce cas, un appel de procédure récursif se produira avant que les instructions ne commencent à être exécutées. La nouvelle instance de la procédure va également, dans un premier temps, appeler une autre instance, et ainsi de suite, jusqu'à atteindre la valeur maximale du compteur. Ce n'est qu'après cela que la dernière des procédures appelées exécutera ses instructions, puis l'avant-dernière exécutera ses instructions, etc. Le résultat de l’appel de LoopImitation2(1, 10) sera d’imprimer les salutations dans l’ordre inverse :

Bonjour N10
…
Bonjour N1

Si nous imaginons une chaîne de procédures appelées de manière récursive, alors dans l'exemple 1, nous la parcourons des procédures appelées précédemment aux procédures ultérieures. Dans l'exemple 2, au contraire, du plus tard au plus tôt.

Enfin, un appel récursif peut être placé entre deux blocs d'instructions. Par exemple:

Procédure LoopImitation3(i, n : entier); commencer writeln("Bonjour N ", je); (Le premier bloc d'instructions peut être situé ici) si je

Ici, les instructions du premier bloc sont d'abord exécutées séquentiellement, puis les instructions du deuxième bloc sont exécutées dans l'ordre inverse. Lors de l’appel de LoopImitation3(1, 10), nous obtenons :

Bonjour N1
…
Bonjour N10
Bonjour N10
…
Bonjour N1

Il faudrait deux boucles pour faire la même chose sans récursion.

Vous pouvez profiter du fait que l’exécution de parties d’une même procédure est espacée dans le temps. Par exemple:

Exemple 3 : Conversion d'un nombre en binaire.

Comme on le sait, l'obtention des chiffres d'un nombre binaire s'effectue en divisant avec un reste par la base du système numérique 2. S'il existe un nombre, alors son dernier chiffre dans sa représentation binaire est égal à

En prenant toute la partie de division par 2 :

nous obtenons un nombre qui a la même représentation binaire, mais sans le dernier chiffre. Ainsi, il suffit de répéter les deux opérations ci-dessus jusqu'à ce que le champ de division suivant reçoive une partie entière égale à 0. Sans récursion cela ressemblera à ceci :

Tant que x>0 commencez c:=x mod 2; x :=x div 2 ; écrire(c); fin;

Le problème ici est que les chiffres de la représentation binaire sont calculés dans l'ordre inverse (le plus récent en premier). Pour imprimer un nombre sous forme normale, vous devrez vous souvenir de tous les nombres contenus dans les éléments du tableau et les imprimer dans une boucle séparée.

En utilisant la récursivité, il n'est pas difficile d'obtenir une sortie dans le bon ordre sans tableau ni seconde boucle. À savoir:

Procédure BinaryRepresentation(x : entier); var c, x : entier ; commencer (Premier bloc. Exécuté dans l'ordre des appels de procédure) c:= x mod 2; x := x div 2 ; (Appel récursif) si x>0 alors BinaryRepresentation(x); (Deuxième bloc. Exécuté dans l'ordre inverse) write(c); fin;

D'une manière générale, nous n'avons reçu aucun gain. Les chiffres de la représentation binaire sont stockés dans des variables locales, qui sont différentes pour chaque instance en cours d'exécution de la procédure récursive. Autrement dit, il n'a pas été possible de sauvegarder la mémoire. Au contraire, nous gaspillons de la mémoire supplémentaire en stockant de nombreuses variables locales x. Cependant, cette solution me semble belle.

4. Relations de récurrence. Récursivité et itération

Une séquence de vecteurs est dite donnée par une relation de récurrence si le vecteur initial et la dépendance fonctionnelle du vecteur suivant par rapport au précédent sont donnés

Un exemple simple de quantité calculée à l'aide de relations de récurrence est la factorielle

La factorielle suivante peut être calculée à partir de la précédente comme suit :

En introduisant la notation , on obtient la relation :

Les vecteurs de la formule (1) peuvent être interprétés comme des ensembles de valeurs variables. Ensuite, le calcul de l'élément requis de la séquence consistera en une mise à jour répétée de leurs valeurs. En particulier pour les factorielles :

X := 1 ; pour i:= 2 à n faire x:= x * i; écrire(x);

Chacune de ces mises à jour (x:= x * i) est appelée itération, et le processus de répétition des itérations est itération.

Notons cependant que la relation (1) est une définition purement récursive de la suite et que le calcul du nième élément est en réalité la prise répétée de la fonction f sur elle-même :

En particulier, pour factorielle on peut écrire :

Fonction Factorielle(n : entier) : entier ; commencer si n > 1 alors Factorial:= n * Factorial(n-1) else Factorial:= 1; fin;

Il faut comprendre que l'appel de fonctions entraîne une surcharge supplémentaire, donc la première option de calcul de la factorielle sera légèrement plus rapide. En général, les solutions itératives fonctionnent plus rapidement que les solutions récursives.

Avant de passer aux situations où la récursivité est utile, regardons un autre exemple où elle ne devrait pas être utilisée.

Considérons un cas particulier de relations récurrentes, lorsque la valeur suivante de la séquence ne dépend pas d'une, mais de plusieurs valeurs précédentes à la fois. Un exemple est la célèbre séquence de Fibonacci, dans laquelle chaque élément suivant est la somme des deux précédents :

Avec une approche « frontale », vous pouvez écrire :

Fonction Fib(n : entier) : entier ; commencer si n > 1 alors Fib := Fib(n-1) + Fib(n-2) sinon Fib := 1 ; fin;

Chaque appel Fib crée deux copies de lui-même, chaque copie en crée deux autres, et ainsi de suite. Le nombre d'opérations augmente avec le nombre n exponentiellement, bien qu'avec une solution itérative linéaire en n nombre d'opérations.

En fait, l’exemple ci-dessus nous apprend non QUAND la récursivité ne doit pas être utilisée, sinon COMMENT il ne devrait pas être utilisé. Après tout, s’il existe une solution itérative rapide (basée sur une boucle), alors la même boucle peut être implémentée à l’aide d’une procédure ou d’une fonction récursive. Par exemple:

// x1, x2 – conditions initiales (1, 1) // n – numéro de la fonction numérique de Fibonacci requise Fib(x1, x2, n : entier) : entier ; var x3 : entier ; commencer si n > 1 alors commencer x3 := x2 + x1 ; x1 := x2 ; x2 := x3 ; Fibonacci := Fibonacci(x1, x2, n-1); fin sinon Fib:= x2; fin;

Néanmoins, les solutions itératives sont préférables. La question est : quand faut-il utiliser la récursivité dans ce cas ?

Toutes les procédures et fonctions récursives qui contiennent un seul appel récursif à elles-mêmes peuvent être facilement remplacées par des boucles itératives. Pour obtenir quelque chose qui n'a pas de contrepartie simple et non récursive, vous devez recourir à des procédures et des fonctions qui s'appellent elles-mêmes deux fois ou plus. Dans ce cas, l’ensemble des procédures appelées ne forme plus une chaîne, comme dans la Fig. 1, mais un arbre entier. Il existe de nombreuses catégories de problèmes pour lesquels le processus informatique doit être organisé de cette manière. Pour eux, la récursivité sera la solution la plus simple et la plus naturelle.

5. Arbres

La base théorique des fonctions récursives qui s'appellent elles-mêmes plus d'une fois est la branche des mathématiques discrètes qui étudie les arbres.

5.1. Définitions basiques. Façons de représenter les arbres

Définition: nous appellerons l'ensemble fini T, constitué d'un ou plusieurs nœuds tels que :
a) Il existe un nœud spécial appelé racine de cet arbre.
b) Les nœuds restants (à l'exclusion de la racine) sont contenus dans des sous-ensembles disjoints par paires, dont chacun est à son tour un arbre. Les arbres sont appelés sous-arbres de cet arbre.

Cette définition est récursive. En bref, un arbre est un ensemble constitué d’une racine et de sous-arbres qui lui sont attachés, qui sont aussi des arbres. Un arbre se définit par lui-même. Cependant cette définition a du sens, puisque la récursion est finie. Chaque sous-arbre contient moins de nœuds que son arbre contenant. En fin de compte, nous arrivons à des sous-arbres contenant un seul nœud, et cela est déjà clair de quoi il s'agit.

Riz. 3. Arbre.

En figue. La figure 3 montre un arbre à sept nœuds. Bien que les arbres ordinaires poussent de bas en haut, il est d'usage de les dessiner dans l'autre sens. Lorsque l’on dessine un diagramme à la main, cette méthode est évidemment plus pratique. En raison de cette incohérence, une confusion survient parfois lorsqu’un nœud est considéré comme étant au-dessus ou en dessous d’un autre. Pour cette raison, il est plus pratique d'utiliser la terminologie utilisée pour décrire les arbres généalogiques, en appelant les nœuds les plus proches des ancêtres racines et les descendants les plus éloignés.

Un arbre peut être représenté graphiquement d’autres manières. Certains d'entre eux sont présentés sur la Fig. 4. Selon la définition, un arbre est un système d'ensembles imbriqués, dans lesquels ces ensembles soit ne se croisent pas, soit sont complètement contenus les uns dans les autres. De tels ensembles peuvent être représentés comme des régions sur un plan (Fig. 4a). En figue. 4b, les ensembles imbriqués ne sont pas situés sur un plan, mais sont allongés en une seule ligne. Riz. 4b peut également être considéré comme un diagramme d'une formule algébrique contenant des parenthèses imbriquées. Riz. La figure 4c donne une autre manière courante de représenter une structure arborescente sous forme de liste échelonnée.

Riz. 4. Autres façons de représenter les structures arborescentes : (a) ensembles imbriqués ; (b) des parenthèses imbriquées ; (c) liste des concessions.

La liste échelonnée présente des similitudes évidentes avec la méthode de formatage code de programme. En effet, un programme écrit dans le cadre du paradigme de programmation structurée peut être représenté comme un arbre constitué de structures imbriquées.

Vous pouvez également faire une analogie entre une liste de rebords et apparence tables des matières dans les livres dont les sections contiennent des sous-sections, qui à leur tour contiennent des sous-sections, etc. Façon traditionnelle La numérotation de ces sections (section 1, sous-sections 1.1 et 1.2, sous-section 1.1.2, etc.) est appelée le système décimal Dewey. Appliqué à l’arbre de la Fig. 3 et 4 ce système donnera :

1. Un ; 1.1B ; 1,2 °C ; 1.2.1D ; 1.2.2E ; 1.2.3 F ; 1.2.3.1G ;

5.2. Passer des arbres

Dans tous les algorithmes liés aux structures arborescentes, la même idée apparaît invariablement, à savoir l'idée qui passe ou parcours d'arbre. C'est une façon de visiter les nœuds de l'arbre dans lesquels chaque nœud est traversé exactement une fois. Il en résulte une disposition linéaire des nœuds de l’arbre. En particulier, il existe trois manières : vous pouvez parcourir les nœuds dans l'ordre avant, arrière et final.

Algorithme de traversée vers l'avant :

• Accédez à la racine
• Parcourez tous les sous-arbres de gauche à droite dans l’ordre direct.

Cet algorithme est récursif, puisque le parcours d'un arbre contient le parcours de sous-arbres, et ceux-ci, à leur tour, sont parcourus en utilisant le même algorithme.

En particulier, pour l’arbre de la Fig. 3 et 4, le parcours direct donne une séquence de nœuds : A, B, C, D, E, F, G.

La séquence résultante correspond à une énumération séquentielle de nœuds de gauche à droite lors de la représentation d'un arbre à l'aide de parenthèses imbriquées et dans système décimal Dewey, ainsi que le passage descendant lorsqu'il est présenté sous la forme d'une liste échelonnée.

Lors de l'implémentation de cet algorithme dans un langage de programmation, atteindre la racine correspond à la procédure ou à la fonction effectuant certaines actions, et parcourir les sous-arbres correspond à des appels récursifs à elle-même. En particulier, pour un arbre binaire (où chaque nœud possède au plus deux sous-arbres), la procédure correspondante ressemblerait à ceci :

// Traversée de précommande – nom anglais pour la procédure de commande à terme PreorderTraversal((Arguments)); commencer //Passer la racine DoSomething((Arguments)); //Transition du sous-arbre gauche if (Il y a un sous-arbre gauche) then PreorderTransversal((Arguments 2)); //Transition du sous-arbre droit if (Il y a un sous-arbre droit) then PreorderTransversal((Arguments 3)); fin;

Autrement dit, la procédure effectue d'abord toutes les actions, et ensuite seulement tous les appels récursifs se produisent.

Algorithme de parcours inverse :

• Parcourez le sous-arbre de gauche,
• Accédez à la racine
• Parcourez le sous-arbre suivant à gauche.
• Accédez à la racine
• etc. jusqu'à ce que le sous-arbre le plus à droite soit parcouru.

Autrement dit, tous les sous-arbres sont parcourus de gauche à droite et le retour à la racine se situe entre ces parcours. Pour l'arbre de la Fig. 3 et 4 cela donne la séquence de nœuds : B, A, D, C, E, G, F.

Dans une procédure récursive correspondante, les actions seront situées dans les espaces entre les appels récursifs. Spécifiquement pour un arbre binaire :

// Inorder Traversal – Nom anglais de la procédure d'ordre inverse InorderTraversal((Arguments)); commencer //Parcourir le sous-arbre gauche if (Un sous-arbre gauche existe) then InorderTraversal((Arguments 2)); //Passer la racine DoSomething((Arguments)); //Parcourir le sous-arbre droit if (Un sous-arbre droit existe) then InorderTraversal((Arguments 3)); fin;

Algorithme de parcours d'ordre final :

• Parcourez tous les sous-arbres de gauche à droite,
• Accédez à la racine.

Pour l'arbre de la Fig. 3 et 4 cela donnera la séquence de nœuds : B, D, E, G, F, C, A.

Dans une procédure récursive correspondante, les actions seront situées après les appels récursifs. Spécifiquement pour un arbre binaire :

// Postorder Traversal – Nom anglais de la procédure de commande de fin PostorderTraversal((Arguments)); commencer //Parcourir le sous-arbre gauche if (Il y a un sous-arbre gauche) then PostorderTraversal((Arguments 2)); // Transcender le sous-arbre droit if (Un sous-arbre droit existe) then PostorderTraversal((Arguments 3)); //Passer la racine DoSomething((Arguments)); fin;

5.3. Représentation d'un arbre dans la mémoire d'un ordinateur

Si certaines informations se trouvent dans des nœuds d’arborescence, une structure de données dynamique appropriée peut être utilisée pour les stocker. En Pascal, cela se fait en utilisant type de variable un enregistrement contenant des pointeurs vers des sous-arbres du même type. Par exemple, un arbre binaire où chaque nœud contient un entier peut être stocké à l'aide d'une variable de type PTree, décrite ci-dessous :

Tapez PTree = ^TTree ; TTree = enregistrement Inf : entier ; Sous-arbre gauche, Sous-arbre droit : PTree ; fin;

Chaque nœud a un type PTree. Il s'agit d'un pointeur, ce qui signifie que chaque nœud doit être créé en appelant la procédure New dessus. Si le nœud est un nœud feuille, alors ses champs LeftSubTree et RightSubTree reçoivent la valeur néant. DANS sinon Les nœuds LeftSubTree et RightSubTree sont également créés par la procédure New.

Un tel enregistrement est représenté schématiquement sur la Fig. 5.

Riz. 5. Représentation schématique d'un enregistrement de type TTree. L'enregistrement comporte trois champs : Inf – un nombre, LeftSubTree et RightSubTree – des pointeurs vers des enregistrements du même type TTree.

Un exemple d’arborescence composée de tels enregistrements est présenté à la figure 6.

Riz. 6. Un arbre composé d'enregistrements de type TTree. Chaque entrée stocke un nombre et deux pointeurs pouvant contenir soit néant, ou les adresses d'autres enregistrements du même type.

Si vous n'avez jamais travaillé avec des structures constituées d'enregistrements contenant des liens vers des enregistrements du même type, nous vous recommandons de vous familiariser avec le matériel concerné.

6. Exemples d'algorithmes récursifs

6.1. Dessiner un arbre

Considérons l'algorithme pour dessiner l'arbre illustré à la Fig. 6. Si chaque ligne est considérée comme un nœud, alors cette image satisfait pleinement à la définition d'un arbre donnée dans la section précédente.

Riz. 6. Arbre.

La procédure récursive tracerait évidemment une ligne (du tronc jusqu'à la première branche), puis s'appellerait pour dessiner les deux sous-arbres. Les sous-arbres diffèrent de l'arbre qui les contient par les coordonnées de leur point de départ, leur angle de rotation, la longueur du tronc et le nombre de branches qu'ils contiennent (une de moins). Toutes ces différences doivent être considérées comme des paramètres de la procédure récursive.

Un exemple d’une telle procédure, écrite en Delphi, est présenté ci-dessous :

Procédure Tree(Canvas: TCanvas; //Canvas sur lequel l'arbre sera dessiné x,y: étendu; //Coordonnées de la racine Angle: étendu; //Angle auquel l'arbre pousse TrunkLength: étendu; //Longueur du tronc n: entier / /Nombre de branches (combien d'appels //récursifs supplémentaires restent)); var x2, y2 : étendu ; //Fin du tronc (point de branchement) début x2:= x + TrunkLength * cos(Angle); y2:= y - Longueur du tronc * sin(Angle); Canvas.MoveTo(rond(x), rond(y)); Canvas.LineTo(rond(x2), rond(y2)); si n > 1 alors commencez Tree(Canvas, x2, y2, Angle+Pi/4, 0.55*TrunkLength, n-1) ; Arbre (Toile, x2, y2, Angle-Pi/4, 0,55*Longueur du tronc, n-1) ; fin; fin;

Pour obtenir la fig. 6, cette procédure a été appelée avec les paramètres suivants :

Arbre (Image1.Canvas, 175, 325, Pi/2, 120, 15) ;

Notez que le dessin est effectué avant les appels récursifs, c'est-à-dire que l'arbre est dessiné dans un ordre direct.

6.2. Tours de Hanoï

Selon la légende, dans le Grand Temple de Bénarès, sous la cathédrale, marquant le milieu du monde, se trouve un disque de bronze sur lequel sont fixées 3 tiges de diamant, hautes d'une coudée et épaisses comme une abeille. Il y a bien longtemps, au tout début des temps, les moines de ce monastère commirent des offenses devant le dieu Brahma. Enragé, Brahma érigea trois hautes tiges et plaça 64 disques d'or pur sur l'un d'eux, de sorte que chaque disque plus petit reposait sur un disque plus grand. Dès que les 64 disques seront transférés de la tige sur laquelle Dieu Brahma les a placés lors de la création du monde, vers une autre tige, la tour ainsi que le temple se transformeront en poussière et le monde périra sous les coups de tonnerre.
Le processus exige que disque plus grand je ne me suis jamais retrouvé au-dessus de rien de moins. Les moines sont confrontés à un dilemme : dans quel ordre doivent-ils effectuer les quarts de travail ? Il est nécessaire de leur fournir un logiciel permettant de calculer cette séquence.

Indépendamment de Brahma, ce puzzle a été proposé à la fin du XIXème siècle par le mathématicien français Edouard Lucas. La version vendue utilisait généralement 7 à 8 disques (Fig. 7).

Riz. 7. Puzzle « Tours de Hanoï ».

Supposons qu'il existe une solution pour n-1 disque. Puis pour le changement n disques, procédez comme suit :

1) Changement n-1 disque.
2) Changement nème disque sur la broche libre restante.
3) On déplace la pile de n-1 disque reçu au point (1) en haut n-ième disque.

Parce que pour le cas n= 1 l'algorithme de réarrangement est évident, alors par induction, en utilisant les actions (1) – (3), on peut réorganiser un nombre arbitraire de disques.

Créons une procédure récursive qui imprime toute la séquence de réarrangements pour un nombre donné de disques. Chaque fois qu'une telle procédure est appelée, elle doit imprimer des informations sur un quart de travail (à partir du point 2 de l'algorithme). Pour les réarrangements des points (1) et (3), la procédure s'appellera avec le nombre de disques réduit de un.

//n – nombre de disques //a, b, c – numéros de broches. Le déplacement s'effectue de la broche a, //vers la broche b avec la broche auxiliaire c. procédure Hanoi(n, a, b, c : entier) ; commencer si n > 1 alors commencer Hanoi(n-1, a, c, b) ; writeln(a, " -> ", b); Hanoï(n-1, c, b, a); end else writeln(a, " -> ", b); fin;

Notez que l’ensemble des procédures appelées récursivement forme dans ce cas un arbre parcouru dans l’ordre inverse.

6.3. Analyser des expressions arithmétiques

Tâche analyse consiste à calculer la valeur de l'expression en utilisant une ligne existante contenant une expression arithmétique et les valeurs connues des variables qui y sont incluses.

Le processus de calcul d’expressions arithmétiques peut être représenté comme un arbre binaire. En effet, chacun des opérateurs arithmétiques (+, –, *, /) nécessite deux opérandes, qui seront également des expressions arithmétiques et, par conséquent, pourront être considérées comme des sous-arbres. Riz. La figure 8 montre un exemple d'arbre correspondant à l'expression :

Riz. 8. Arbre syntaxique correspondant à l'expression arithmétique (6).

Dans un tel arbre, les nœuds d'extrémité seront toujours des variables (ici X) ou des constantes numériques, et tous les nœuds internes contiendront des opérateurs arithmétiques. Pour exécuter un opérateur, vous devez d'abord évaluer ses opérandes. Ainsi, l’arbre de la figure doit être parcouru dans l’ordre terminal. Séquence de nœuds correspondante

appelé notation polonaise inversée expression arithmétique.

Lors de la construction d’un arbre syntaxique, vous devez faire attention à la fonctionnalité suivante. Si, par exemple, il existe une expression

et nous lirons les opérations d'addition et de soustraction de gauche à droite, alors l'arbre syntaxique correct contiendra un moins au lieu d'un plus (Fig. 9a). En substance, cet arbre correspond à l'expression. Il est possible de faciliter la création d'un arbre si vous analysez l'expression (8) à l'envers, de droite à gauche. Dans ce cas, le résultat est un arbre avec la Fig. 9b, équivalent à l'arbre 8a, mais ne nécessitant pas de remplacement de signalisation.

De même, de droite à gauche, vous devez analyser les expressions contenant des opérateurs de multiplication et de division.

Riz. 9. Arbres syntaxiques pour l'expression un – b + c lors de la lecture de gauche à droite (a) et de droite à gauche (b).

Cette approche n'élimine pas complètement la récursivité. Cependant, cela permet de se limiter à un seul appel à une procédure récursive, ce qui peut être suffisant si l'on cherche à maximiser les performances.

7.3. Déterminer un nœud d'arbre par son numéro

L'idée de cette approche est de remplacer les appels récursifs par une simple boucle qui sera exécutée autant de fois qu'il y a de nœuds dans l'arbre formé par les procédures récursives. Ce qui sera fait exactement à chaque étape doit être déterminé par le numéro de l'étape. Faites correspondre le numéro de l'étape et actions nécessaires– la tâche n’est pas anodine et dans chaque cas elle devra être résolue séparément.

Par exemple, disons que vous voulez faire k boucles imbriquées nétapes dans chacun :

Pour i1 := 0 à n-1 faire pour i2 := 0 à n-1 faire pour i3 := 0 à n-1 faire …

Si k est inconnu à l’avance, il est impossible de les écrire explicitement, comme indiqué ci-dessus. En utilisant la technique démontrée à la section 6.5, vous pouvez obtenir le nombre requis de boucles imbriquées en utilisant une procédure récursive :

Procédure NestedCycles(Index : tableau d'entiers ; n, k, profondeur : entier) ; var i : entier ; commencer si profondeur

Pour vous débarrasser de la récursion et tout réduire à un seul cycle, notez que si vous numérotez les étapes dans le système de numérotation de base n, alors chaque étape a un numéro composé des nombres i1, i2, i3, ... ou des valeurs correspondantes du tableau Index. C'est-à-dire que les nombres correspondent aux valeurs des compteurs de cycles. Numéro d'étape en notation décimale régulière :

Il y aura un total d'étapes nk. En parcourant leurs nombres dans le système de nombres décimaux et en convertissant chacun d'eux au système de base n, nous obtenons les valeurs d'index :

M:= rond(IntPower(n, k)); pour i:= 0 à M-1, commencez Number:= i; pour p:= 0 à k-1, commencez Index := Nombre mod n; Nombre := Nombre div n ; fin; Faire quelque chose (index); fin;

Notons encore une fois que la méthode n'est pas universelle et qu'il faudra inventer quelque chose de différent pour chaque tâche.

Questions de contrôle

1. Déterminez ce que feront les procédures et fonctions récursives suivantes.

(a) Qu'imprimera la procédure suivante lorsque Rec(4) sera appelé ?

Procédure Rec(a : entier) ; commencer à écrire(a); si a>0 alors Rec(a-1); écrire(a); fin;

(b) Quelle sera la valeur de la fonction Nod(78, 26) ?

Fonction Nod(a, b : entier) : entier ; commencer si a > b alors Nod := Nod(a – b, b) sinon si b > a then Nod := Nod(a, b – a) else Nod := a ; fin;

(c) Qu'est-ce qui sera imprimé par les procédures ci-dessous lorsque A(1) est appelé ?

Procédure A(n : entier) ; procédure B(n : entier) ; procédure A(n : entier) ; commencer writeln(n); B(n-1); fin; procédure B(n : entier) ; commencer writeln(n); si n

(d) Que la procédure ci-dessous imprimera-t-elle lors de l'appel de BT(0, 1, 3) ?

Procédure BT(x : réel ; D, MaxD : entier) ; commencer si D = MaxD alors écrire ln(x) sinon commencer BT(x – 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); fin; fin;

2. Ouroboros - un serpent dévorant sa propre queue (Fig. 14) lorsqu'il est déplié a une longueur L, diamètre autour de la tête D, épaisseur de la paroi abdominale d. Déterminez combien de queue il peut insérer en lui-même et combien de couches la queue sera-t-elle ensuite posée ?

Riz. 14. Ouroboros élargis.

3. Pour l’arbre de la Fig. 10a indique la séquence des nœuds visiteurs dans l'ordre de parcours avant, arrière et final.

4. Représentez graphiquement l'arbre défini à l'aide de parenthèses imbriquées : (A(B(C, D), E), F, G).

5. Représentez graphiquement l'arbre syntaxique de l'expression arithmétique suivante :

Écrivez cette expression en notation polonaise inversée.

6. Pour le graphique ci-dessous (Fig. 15), notez la matrice de contiguïté et la matrice d'incidence.

Tâches

1. Après avoir suffisamment calculé la factorielle un grand nombre de fois (un million ou plus), comparez l’efficacité des algorithmes récursifs et itératifs. Dans quelle mesure le temps d'exécution sera-t-il différent et comment ce rapport dépendra-t-il du nombre dont la factorielle est calculée ?

2. Écrivez une fonction récursive qui vérifie si les parenthèses sont correctement placées dans une chaîne. Si l'arrangement est correct, les conditions suivantes sont remplies :

(a) le nombre de parenthèses ouvrantes et fermantes est égal.
(b) dans chaque paire, il y a une parenthèse d'ouverture - de fermeture correspondante, les parenthèses sont placées correctement.

Exemples de placement incorrect :)(, ())(, ())((), etc.

3. La ligne peut contenir à la fois des crochets et des crochets. Chaque parenthèse ouvrante a une parenthèse fermante correspondante du même type (rond - rond, carré - carré). Écrivez une fonction récursive qui vérifie si les parenthèses sont correctement placées dans ce cas.

Exemple de placement incorrect : ([)].

4. Le nombre de structures de parenthèses régulières de longueur 6 est 5 : ()()(), (())(), ()(()), ((())), (()()).
Écrivez un programme récursif pour générer toutes les structures de parenthèses régulières de longueur 2 n.

Note: Corriger la structure des parenthèses de longueur minimale "()". Les structures de plus grande longueur sont obtenues à partir de structures de plus courte longueur de deux manières :

a) si la structure la plus petite est mise entre parenthèses :
(b) si deux structures plus petites sont écrites séquentiellement.

5. Créez une procédure qui imprime toutes les permutations possibles pour les entiers de 1 à N.

6. Créez une procédure qui imprime tous les sous-ensembles de l'ensemble (1, 2, ..., N).

7. Créez une procédure qui imprime toutes les représentations possibles de l'entier naturel N comme la somme d'autres nombres naturels.

8. Créez une fonction qui calcule la somme des éléments du tableau en utilisant l'algorithme suivant : le tableau est divisé en deux, les sommes des éléments de chaque moitié sont calculées et additionnées. La somme des éléments de la moitié du tableau est calculée à l'aide du même algorithme, c'est-à-dire encore une fois en divisant par deux. Les divisions se produisent jusqu'à ce que les éléments résultants du tableau contiennent chacun un élément et le calcul de la somme devient donc trivial.

Commentaire: Cet algorithme est une alternative. Dans le cas de tableaux à valeurs réelles, cela permet généralement des erreurs d'arrondi plus petites.

10. Créez une procédure qui dessine la courbe de Koch (Figure 12).

11. Reproduisez la figure. 16. Dans la figure, à chaque itération suivante, le cercle est 2,5 fois plus petit (ce coefficient peut devenir un paramètre).

Littérature

1. D. Knuth. L'art de la programmation informatique. v. 1. (section 2.3. « Arbres »).
2. N. Wirth. Algorithmes et structures de données.

Algorithme récursif

Récursivité- une méthode de définition d'une classe d'objets ou de méthodes en spécifiant d'abord un ou plusieurs (généralement simples) basique cas ou méthodes, puis en définissant à partir d'eux une règle pour construire une classe définie qui fait référence directement ou indirectement à ces cas de base.

En d’autres termes, la récursivité est un moyen définition générale objet ou action à travers soi-même, en utilisant des définitions privées préalablement définies. La récursivité est utilisée lorsque l'autosimilarité d'un problème peut être identifiée.

Exemples

Algorithme de déplacement de la tour, l'algorithme déplacera le nombre de disques requis de la pyramide « source » vers la pyramide « tâche » en utilisant la pyramide « de rechange ».

Si le nombre de disques est un, alors :

• Déplacer le disque de la source vers le travail

Sinon:

• Déplacez de manière récursive tous les disques sauf un de la source vers le disque de secours, en utilisant le travail comme disque de secours.
• Déplacer le disque restant de la source vers le travail
• Déplacez tous les disques du stock vers le travail en utilisant la source comme stock

Récursivité en programmation

Les fonctions

Classe element_of_list ( element_of_list *next; /* référence à l'élément suivant du même type */ données entières ; /* certaines données */ ) ;

La structure récursive des données dicte souvent le recours à la récursivité pour traiter les données.

Récursion en physique

Un exemple classique de récursivité infinie est celui de deux miroirs placés l'un en face de l'autre : ils forment deux couloirs de reflets décolorés des miroirs.

Un autre exemple de récursivité infinie est l'effet d'auto-excitation (rétroaction positive) dans circuits électroniques L'amplification, lorsque le signal de la sortie atteint l'entrée, est amplifiée, atteint à nouveau l'entrée du circuit et est à nouveau amplifiée. Les amplificateurs pour lesquels ce mode de fonctionnement est standard sont appelés auto-oscillateurs.

Récursion en linguistique

La capacité d'un langage à générer des phrases et des constructions imbriquées. Offre de base le chat a mangé la souris peut être étendu par récursion comme Vanya a deviné que le chat avait mangé la souris, alors comme Katya sait que Vanya a deviné que le chat avait mangé la souris et ainsi de suite. La récursion est considérée comme l'un des universaux linguistiques, c'est-à-dire qu'elle est caractéristique de toute langue naturelle (bien qu'en Dernièrement discuté activement absence possible récursivité dans l'une des langues de l'Amazonie - le pirahã, notée par le linguiste D. Everett). La récursion en linguistique, ses variétés et les manifestations les plus caractéristiques de la langue russe sont décrites dans l'article de E.A. Lodatko « Structures linguistiques récursives » (voir : Structures linguistiques récursives)

Citations

Humour

La plupart des blagues sur la récursivité concernent la récursivité infinie, qui n'a pas de condition de sortie. Dictons célèbres : « Pour comprendre la récursion, il faut d'abord comprendre la récursion », « Pour faire quelque chose, il faut faire quelque chose », « Pour préparer une salade, il faut : des concombres, des tomates, de la laitue ». Une blague très populaire sur la récursivité, qui rappelle une entrée de dictionnaire :

Plusieurs récits de Stanislaw Lem sont consacrés à des (possibles) incidents à récursion infinie :

• L'histoire d'Ion le Tranquille « Le quatorzième voyage » du « Star Diaries of Iyon the Quiet », dans laquelle le héros passe successivement d'un article sur les sépulki à un article sur la sépullation, de là à un article sur les sépulcaria, qui contient à nouveau une référence à l'article « sepulki ».
• L'histoire d'une machine intelligente qui avait suffisamment d'intelligence et de paresse pour en construire une similaire pour résoudre un problème donné et lui confier la solution (le résultat était une récursion sans fin, lorsque chaque nouvelle machine en construisait une similaire et déléguait la tâche à il).

La chanson du conte populaire russe « Le prêtre avait un chien... » est un exemple de récursion :

Le curé avait un chien, il l'adorait,
Elle a mangé un morceau de viande, il l'a tuée.
Enterré dans le sol
Légende a écrit :

« Le curé avait un chien, il l'aimait, Elle mangeait un morceau de viande, il la tua, Il l'enterra en terre, L'inscription était écrite : « Le curé avait un chien, il l'aimait, Elle mangea un morceau de viande. viande, il l'a tuée, Il l'a enterrée dans le sol, Inscription écrite : ...

voir également

• Séquence récurrente (séquence de retour)

Liens

• Thomas H. Corman, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein Algorithmes : construction et analyse = INTRODUCTION AUX ALGORITHMES. - 2e éd. - M. : "Williams", 2006. - P. 1296. - ISBN 0-07-013151-1

Fondation Wikimédia. 2010.

Découvrez ce qu'est un « algorithme récursif » dans d'autres dictionnaires :

algorithme récursif- rekursyvusis algoritmas statusas T sritis automatika atitikmenys: engl. algorithme récursif vok. Algorithme rekursiver, m rus. algorithme récursif, m pran. algorithme récursif, m … Automatikos terminų žodynas

algorithme de contrôle récursif- rekursyvusis valdymo algoritmas statusas T sritis automatika atitikmenys : engl. algorithme de contrôle récursif vok. rekursiver Regelungs od. Algorithme de Steuerungs, m rus. algorithme de contrôle récursif, m pranc. algorithme de réglage récurrent, m … Automatikos terminų žodynas

Il s'agit d'un algorithme pour classer les éléments dans une liste. Lorsqu'un élément de liste comporte plusieurs champs, le champ qui sert de critère d'ordre est appelé clé de tri. En pratique, un numéro est souvent utilisé comme clé, et dans d'autres domaines... ... Wikipédia

Acronyme récursif Acronyme (parfois un backronym) qui fait référence à lui-même. Dans l'environnement pirates informatiques Il est devenu traditionnel de choisir des acronymes et des abréviations qui font référence à eux-mêmes indirectement ou directement. L'un des premiers exemples... ... Wikipédia

- (Anglais : Analyseur de descente récursive) un algorithme d'analyse implémenté en appelant mutuellement des procédures d'analyse conformes aux règles de grammaire sans contexte ou BNF. Application des règles de manière séquentielle, de gauche à droite... Wikipédia

Une méthode récursive pour créer un maillage de coupe afin de diviser plusieurs polygones 2D contenant des îles en zones sans îles. Peut être utilisé dans Systèmes d'information géographique pour convertir des polygones insulaires en polygones non insulaires. Attacher? ... Wikipédia

Ce terme a d'autres significations, voir Algorithme (significations). Améliorer cet article, est-ce souhaitable ? : Retravailler le design dans le respect des règles... Wikipédia

Algorithmes de recherche de graphiques A* B* Algorithme de Bellman Ford Recherche bidirectionnelle Algorithme de Dijkstra Algorithme de Johnson Recherche en largeur d'abord Recherche en profondeur d'abord Recherche limitée en profondeur Recherche de première meilleure correspondance Algorithme de Floyd Warshall Recherche... ... Wikipedia

Ce terme a d'autres significations, voir Ppm. PPM (Prediction by Partial Matching) est un algorithme adaptatif de compression de données statistique sans perte basé sur le contexte... ... Wikipedia

La récursivité est un phénomène assez courant qui se produit non seulement dans le domaine scientifique, mais aussi dans la vie quotidienne. Par exemple, l'effet Droste, le triangle de Sierpinski, etc. Le moyen le plus simple de voir la récursion est de pointer la webcam vers l'écran de l'ordinateur, bien sûr, après l'avoir d'abord allumée. Ainsi, la caméra enregistrera l'image de l'écran de l'ordinateur et l'affichera sur cet écran, ce sera quelque chose comme une boucle fermée. En conséquence, nous observerons quelque chose de similaire à un tunnel.

En programmation, la récursivité est étroitement liée aux fonctions, plus précisément, c'est grâce aux fonctions en programmation qu'il existe une récursivité ou une fonction récursive. En termes simples, la récursion est la définition d'une partie d'une fonction (méthode) à travers elle-même, c'est-à-dire qu'il s'agit d'une fonction qui s'appelle, directement (dans son corps) ou indirectement (à travers une autre fonction). Les problèmes récursifs typiques sont : trouver n !, nombres de Fibonacci. Nous avons déjà résolu de tels problèmes, mais en utilisant des boucles, c'est-à-dire de manière itérative. D’une manière générale, tout ce qui est résolu de manière itérative peut être résolu de manière récursive, c’est-à-dire en utilisant une fonction récursive. Toute la solution consiste à résoudre le cas principal ou, comme on l'appelle aussi, le cas de base. Il existe une étape de récursion ou un appel récursif. Dans le cas où une fonction récursive est appelée pour résoudre un problème complexe (pas le cas de base), un certain nombre d'appels ou d'étapes récursifs sont effectués afin de réduire le problème à un problème plus simple. Et ainsi de suite jusqu'à ce que nous obtenions une solution de base. Développons un programme qui déclare une fonction récursive qui calcule n !

"stdafx.h" #include << "Enter n!: "; cin >>n; cout<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

// code Code :: Blocs

// Code Dev-C++

// factorial.cpp : Définit le point d'entrée de l'application console. #inclure en utilisant l'espace de noms std ; unsigned long int factorial(unsigned long int); // prototype d'une fonction récursive int i = 1; // initialisation d'une variable globale pour compter le nombre d'appels récursifs unsigned long int result; // variable globale pour stocker le résultat renvoyé de la fonction récursive int main(int argc, char* argv) ( int n; // variable locale pour transmettre le nombre saisi depuis le clavier cout<< "Enter n!: "; cin >>n; cout<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

DANS lignes 7, 9, 21 Le type de données est déclaré unsigned long int , puisque la valeur de la factorielle augmente très rapidement, par exemple déjà 10 ! = 3 628 800. Si la taille du type de données n'est pas suffisante, le résultat sera une valeur complètement incorrecte. Le code déclare plus d'opérateurs que nécessaire pour trouver n !. Ceci est fait pour qu'après son exécution, le programme montre ce qui se passe à chaque étape des appels récursifs. Veuillez noter les lignes de code en surbrillance, lignes 23, 24, 28 est une solution récursive à n!. Lignes 23, 24 sont la solution de base à une fonction récursive, c'est-à-dire dès que la valeur de la variable F sera égal à 1 ou 0 (puisqu'on sait que 1 ! = 1 et 0 ! = 1), les appels récursifs s'arrêteront, et les valeurs commenceront à être renvoyées pour chaque appel récursif. Lorsque la valeur du premier appel récursif revient, le programme renvoie la valeur de la factorielle calculée. DANS ligne 28 la fonction factorial() s'appelle elle-même, mais son argument est un de moins. L'argument est réduit à chaque fois pour parvenir à une solution particulière. Le résultat du programme (voir Figure 1).

Entrez n!: 5 Résultat de l'étape 1 = 0 Résultat de l'étape 2 = 0 Résultat de l'étape 3 = 0 Résultat de l'étape 4 = 0 5! = 120

Figure 1 - Récursivité en C++

Sur la base du résultat du programme, chaque étape est clairement visible et le résultat à chaque étape est nul, à l'exception du dernier appel récursif. Il a fallu calculer cinq factorielles. Le programme a effectué quatre appels récursifs et au cinquième appel, le scénario de base a été trouvé. Et une fois que le programme a trouvé une solution au cas de base, il a résolu les étapes précédentes et a généré le résultat global. Sur la figure 1, seules quatre étapes sont visibles car dans la cinquième étape une solution partielle a été trouvée, qui a finalement renvoyé la solution finale, c'est-à-dire 120. La figure 2 montre le schéma de calcul récursif 5!. Le diagramme montre clairement que le premier résultat est renvoyé lorsqu'une solution particulière est atteinte, mais pas immédiatement après chaque appel récursif.

Figure 2 - Récursivité en C++

Alors pour en trouver 5 ! il faut en savoir 4 ! et multipliez-le par 5 ; 4 ! = 4*3 ! et ainsi de suite. Selon le schéma illustré à la figure 2, le calcul sera réduit à trouver un cas particulier, c'est-à-dire 1 !, après quoi les valeurs seront renvoyées tour à tour à chaque appel récursif. Le dernier appel récursif renverra la valeur 5!.

Retravaillons le programme de recherche de factorielle afin d'obtenir un tableau de factorielles. Pour ce faire, nous déclarerons une boucle for dans laquelle nous appellerons la fonction récursive.

en utilisant l'espace de noms std ; unsigned long int factorial(unsigned long int); // prototype d'une fonction récursive int i = 1; // initialisation d'une variable globale pour compter le nombre d'appels récursifs unsigned long int result; // variable globale pour stocker le résultat renvoyé de la fonction récursive int main(int argc, char* argv) ( int n; // variable locale pour transmettre le nombre saisi depuis le clavier cout<< "Enter n!: "; cin >>n; pour (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <>n; pour (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i < << "Enter number from the Fibonacci series: "; cin >> <= entered_number; counter++) cout << setw(2) <

// code Code :: Blocs

// Code Dev-C++

// fibonacci.cpp : définit le point d'entrée de l'application console. #inclure // bibliothèque de formatage des informations affichées à l'écran #include en utilisant l'espace de noms std ; unsigned long fibonacci(unsigned long); // prototype d'une fonction récursive pour rechercher des nombres de la série de Fibonacci int main(int argc, char* argv) ( unsigned long enter_number; cout<< "Enter number from the Fibonacci series: "; cin >> numéro_entré ; pour (compteur int = 1 ; compteur<= entered_number; counter++) cout << setw(2) <#inclure en utilisant l'espace de noms std ; tour vide (int, int, int, int); // déclaration d'un prototype de fonction récursive int count = 1; // variable globale pour compter le nombre d'étapes int _tmain(int argc, _TCHAR* argv) ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>numéro ; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> basic_rod; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> tige_finale ; int help_rod; // bloc de détermination du numéro de la tige auxiliaire, analysant les numéros de la tige initiale et finale if (basic_rod != 2 && final_rod != 2) help_rod = 2; sinon if (basic_rod != 1 && final_rod != 1) help_rod = 1; sinon if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(// lancement d'une fonction récursive pour résoudre le problème des Tours de Hanoï numéro, // une variable stockant le nombre de disques à déplacer basic_rod, // une variable stockant le numéro de la tige sur laquelle les disques seront initialement placés situé help_rod , // une variable stockant le numéro de la tige, qui sert d'auxiliaire final_rod); // variable stockant le numéro de la tige vers laquelle les disques doivent être déplacés system("pause"); renvoie 0 ; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // condition de fin des appels récursifs ( cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

// code Code :: Blocs

// Code Dev-C++

// hanoi_tower.cpp : Définit le point d'entrée de l'application console. // Un programme qui résout de manière récursive le problème de la Tour de Hanoi #include #inclure en utilisant l'espace de noms std ; tour vide (int, int, int, int); // déclaration d'un prototype de fonction récursive int count = 1; // variable globale pour compter le nombre d'étapes int main() ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >>numéro ; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> basic_rod; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> tige_finale ; int help_rod; // bloc de détermination du numéro de la tige auxiliaire, analysant les numéros de la tige initiale et finale if (basic_rod != 2 && final_rod != 2) help_rod = 2; sinon if (basic_rod != 1 && final_rod != 1) help_rod = 1; sinon if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(// lancement d'une fonction récursive pour résoudre le problème des Tours de Hanoï numéro, // une variable stockant le nombre de disques à déplacer basic_rod, // une variable stockant le numéro de la tige sur laquelle les disques seront initialement placés situé help_rod , // une variable stockant le numéro de la tige, qui sert d'auxiliaire final_rod); // variable stockant le numéro de la tige vers laquelle les disques doivent être déplacés return 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // condition de fin des appels récursifs ( cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

La figure 5 montre un exemple du programme récursif de la Tour de Hanoï. Tout d'abord, nous avons entré le nombre de disques égal à trois, puis nous avons entré la tige de base (la première) et avons désigné la tige finale (la troisième). Automatiquement la deuxième tige devint auxiliaire. Le programme a produit un résultat qui coïncide complètement avec la solution animée à ce problème.

Saisir le nombre de disques : 3 Saisir le numéro de tige de base : 1 Saisir le nombre de tige finale : 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3

Figure 5 - Récursivité en C++

On peut voir sur la figure que le disque se déplace d'abord de la tige un à la tige trois, puis de la tige un à la tige deux, de la tige trois à la tigedeux, etc. Autrement dit, le programme affiche simplement la séquence de mouvements du disque et le nombre minimum d'étapes au cours desquelles tous les disques seront déplacés.

Tous ces problèmes pourraient être résolus de manière itérative. La question se pose : « Qu’est-ce qu’il est préférable de résoudre, de manière itérative ou récursive ? Je réponds : « L'inconvénient de la récursivité est qu'elle consomme nettement plus de ressources informatiques que l'itération. Cela entraîne une lourde charge à la fois sur la RAM et sur le processeur. S’il est évident qu’un problème particulier peut être résolu de manière itérative, alors il doit être utilisé différemment, en utilisant la récursion ! » En fonction du problème à résoudre, la complexité de l'écriture des programmes change lors de l'utilisation de l'une ou l'autre méthode de solution. Mais le plus souvent, un problème résolu par une méthode récursive du point de vue de la lisibilité du code est beaucoup plus clair et plus court.

YouTube encyclopédique

• 1 / 5

  En mathématiques, la récursion concerne la méthode de définition des fonctions et des séries de nombres : défini de manière récursive une fonction détermine sa valeur en s'appelant avec d'autres arguments. Dans ce cas, deux options sont possibles :

  e = 2 + 2 2 + 3 3 + 4 4 + … = 2 + f (2) (\displaystyle e=2+(\cfrac (2)(2+(\cfrac (3)(3+(\cfrac ( 4)(4+\ldots ))))))\;=2+f(2)), Où f (n) = n n + f (n + 1) (\displaystyle f(n)=(\cfrac (n)(n+f(n+1)))) Un calcul direct utilisant la formule ci-dessus provoquera une récursion infinie, mais il peut être prouvé que la valeur de f(n) tend vers l'unité lorsque n augmente (donc, malgré l'infinité de la série, la valeur du nombre d'Euler est finie ). Pour calculer approximativement la valeur de e, il suffit de limiter artificiellement la profondeur de récursion à un nombre prédéterminé et, une fois atteint, de l'utiliser à la place f (n) (\style d'affichage f(n)) unité.

  Un autre exemple de récursion en mathématiques est une série de nombres donnée par une formule récurrente, lorsque chaque terme suivant de la série est calculé comme le résultat d'une fonction de n termes précédents. Ainsi, à l'aide d'une expression finie (qui est une combinaison d'une formule récurrente et d'un ensemble de valeurs pour les n premiers termes d'une série), la définition d'une série infinie peut être donnée.

  Struct element_of_list ( element_of_list * next ; /* pointeur vers l'élément suivant du même type */ données int ; /* certaines données */ );

  Puisqu’un nombre infini d’objets imbriqués ne peuvent pas être hébergés dans une mémoire finie, en réalité de telles structures définies de manière récursive sont toujours finies. Dans les cellules finales (terminales), des pointeurs vides sont généralement écrits, qui sont également des drapeaux indiquant au programme traitant la structure que sa fin a été atteinte.