Compréhension moderne de la récursivité: définition de la fonctionnalité et accès à celle-ci depuis l'extérieur et depuis cette fonctionnalité. On pense que la récursivité est née des mathématiciens: calcul factoriel, séries infinies, fractales, fractions continues… Pourtant, la récursivité se retrouve partout. Les lois naturelles objectives "considérent" la récursivité comme leur principal algorithme et forme d'expression (existence) non pas tant des objets du monde matériel, mais en général le principal algorithme de mouvement.
Des personnes de diverses spécialités dans divers domaines de la science et de la technologie utilisent l'algorithme récursif f (x), où "x ~/=f (x)". Une fonction qui s'appelle elle-même est une solution forte, mais former et comprendre cette solution est, dans la plupart des cas, une tâche très difficile.
Dans les temps anciens, la récursivité était utilisée pour augmenter l'espace du palais. Grâce à un système de miroirs dirigés les uns vers les autres, vous pouvez créer de superbes effets spatiaux en trois dimensions. Mais est-il si facile de comprendre commentrégler ces rétroviseurs ? Il est encore plus difficile de déterminer où se trouve un point de l'espace, réfléchi par plusieurs miroirs.
Récursion, algorithmes récursifs: signification et syntaxe
Le problème, qui est formulé en répétant une séquence d'opérations, peut être résolu de manière récursive. Un algorithme simple (calculer une équation quadratique, un script pour remplir une page web avec des informations, lire un fichier, envoyer un message…) ne nécessite pas de récursivité.
Principales différences de l'algorithme qui permet une solution récursive:
- il y a un algorithme qui doit être exécuté plusieurs fois;
- l'algorithme a besoin de données qui changent à chaque fois;
- l'algorithme n'a pas à changer à chaque fois;
- il y a une condition finale: l'algorithme est récursif - pas infini.
En général, on ne peut pas prétendre qu'une exécution unique est une condition nécessaire à l'absence de motif de récursivité. Vous ne pouvez pas non plus exiger une condition finale obligatoire: les récursions infinies ont leur propre portée.
L'algorithme est récursif: lorsqu'une séquence d'opérations est effectuée de manière répétée, sur des données qui changent à chaque fois et donnent à chaque fois un nouveau résultat.
Formule de récurrence
La compréhension mathématique de la récursivité et son analogue en programmation sont différents. Les mathématiques, bien qu'il y ait des signes de programmation, mais la programmation est une mathématique d'un ordre beaucoup plus élevé.
Un algorithme bien écrit est comme un miroir de l'intellect de son auteur. Généralla formule de récurrence en programmation est "f(x)", où "x ~/=f(x)" a au moins deux interprétations. Ici "~" est la similarité ou l'absence du résultat, et "=" est la présence du résultat de la fonction.
Première option: dynamique des données.
- la fonction "f(x)" a un algorithme récursif et immuable;
- "x" et le résultat "f(x)" ont de nouvelles valeurs à chaque fois, le résultat "f(x)" est le nouveau paramètre "x" de cette fonction.
Deuxième option: la dynamique du code.
- la fonction "f(x)" a plusieurs algorithmes qui affinent (analysent) les données;
- analyse des données - une partie du code et la mise en œuvre d'algorithmes récursifs qui effectuent l'action souhaitée - la deuxième partie du code;
- le résultat de la fonction "f(x)" n'est pas.
Aucun résultat n'est normal. La programmation n'est pas mathématique, ici le résultat n'a pas à être explicitement présent. Une fonction récursive peut simplement analyser des sites et remplir la base de données, ou instancier des objets en fonction de l'entrée entrante.
Données et récursivité
Programmer des algorithmes récursifs ne consiste pas à calculer une factorielle, dans laquelle la fonction reçoit à chaque fois une valeur donnée qui est un de plus ou de moins que un - l'option d'implémentation dépend de la préférence du développeur.
Peu importe comment le factoriel "8 !",algorithme qui suit strictement cette formule.
Le traitement de l'information est une "mathématique" d'un tout autre ordre. Les fonctions et algorithmes récursifs opèrent ici sur des lettres, des mots, des phrases, des phrases et des paragraphes. Chaque niveau suivant utilise le précédent.
Le flux de données d'entrée est analysé sur un large éventail de conditions, mais le processus d'analyse est généralement récursif. Cela n'a aucun sens d'écrire des algorithmes uniques pour toutes les variantes du flux d'entrée. Il devrait y avoir une fonctionnalité. Ici, les algorithmes récursifs sont des exemples de la manière de former un flux de sortie adapté à l'entrée. Ce n'est pas la sortie de l'algorithme récursif, mais c'est la solution souhaitée et nécessaire.
Abstraction, récursivité et POO
La programmation orientée objet (POO) et la récursivité sont des entités fondamentalement différentes, mais elles se complètent parfaitement. L'abstraction n'a rien à voir avec la récursivité, mais à travers le prisme de la POO, elle crée la possibilité d'implémenter la récursivité contextuelle.
Par exemple, les informations sont analysées et les lettres, mots, expressions, phrases et paragraphes sont mis en surbrillance séparément. Évidemment, le développeur prévoira la création d'instances d'objets de ces cinq types et proposera une solution d'algorithmes récursifs à chaque niveau.
En attendant, si au niveau des lettres "il ne sert à rien de chercher du sens", alors la sémantique apparaît au niveau des mots. Vous pouvez diviser les mots en verbes, noms, adverbes, prépositions… Vous pouvez aller plus loin et définir des cas.
Au niveau de la phrase, la sémantique est complétée par des signes de ponctuation et une logiquecombinaisons de mots. Au niveau des phrases, on trouve un niveau de sémantique plus parfait, et un paragraphe peut être considéré comme une pensée complète.
Le développement orienté objet prédétermine l'héritage des propriétés et des méthodes et propose de commencer la hiérarchie des objets par la création d'un ancêtre complètement abstrait. En même temps, sans doute, l'analyse de chaque descendant sera récursive et ne différera pas trop au niveau technique dans de nombreuses positions (lettres, mots, phrases et phrases). Les paragraphes, comme les pensées complètes, peuvent se démarquer de cette liste, mais ils n'en sont pas l'essence.
Il est important que la majeure partie de l'algorithme puisse être formulée au niveau de l'ancêtre abstrait, en l'affinant au niveau de chaque descendant avec des données et des méthodes appelées depuis le niveau abstrait. Dans ce contexte, l'abstraction ouvre de nouveaux horizons à la récursivité.
Caractéristiques historiques de la POO
La POO est venue deux fois dans le monde des logiciels, bien que certains experts puissent considérer l'émergence du cloud computing et des idées modernes sur les objets et les classes comme un nouveau cycle dans le développement des technologies informatiques.
Les termes "objet" et "objectif" dans le contexte moderne de la POO sont généralement attribués aux années 50 et 60 du siècle dernier, mais ils sont associés à 1965 et à l'émergence de Simula, Lisp, Algol, Smalltalk.
À cette époque, la programmation n'était pas particulièrement développée et ne pouvait pas répondre adéquatement aux concepts révolutionnaires. La lutte des idées et des styles de programmation (C / C ++ et Pascal - principalement) était encore loin et les bases de données étaient encore conceptuellement formées.
À la fin des années 80 et au début des années 90, les objets sont apparus en Pascal et tout le monde se souvenait des cours en C / C++ - cela a marqué un nouveau cycle d'intérêt pour la POO et c'est alors que les outils, principalement les langages de programmation, sont devenus non ne prennent en charge que les idées orientées objet, mais évoluent en conséquence.
Bien sûr, si les algorithmes récursifs antérieurs n'étaient que des fonctions utilisées dans le code général du programme, la récursivité pourrait désormais faire partie des propriétés d'un objet (classe), ce qui offrait des opportunités intéressantes dans le contexte de l'héritage.
Fonctionnalité de la POO moderne
Le développement de la POO a initialement déclaré des objets (classes) comme des collections de données et de propriétés (méthodes). En fait, il s'agissait de données qui ont une syntaxe et une signification. Mais alors il n'était pas possible de présenter la POO comme un outil de gestion d'objets réels.
OOP est devenu un outil de gestion d'objets "nature informatique". Un script, un bouton, un élément de menu, une barre de menu, une balise dans une fenêtre de navigateur est un objet. Mais pas une machine, un produit alimentaire, un mot ou une phrase. Les objets réels sont restés en dehors de la programmation orientée objet et les outils informatiques ont pris une nouvelle incarnation.
En raison des différences entre les langages de programmation populaires, de nombreux dialectes de la POO ont émergé. En termes de sémantique, ils sont pratiquement équivalents, et leur focalisation sur la sphère instrumentale, et non appliquée, permet de porter la description d'objets réels au-delàalgorithmes et assurer leur "existence" multiplateforme et interlangue
Piles et mécanismes d'appel de fonction
Les mécanismes d'appel de fonctions (procédures, algorithmes) nécessitent de transmettre des données (paramètres), de renvoyer un résultat et de se souvenir de l'adresse de l'opérateur qui doit recevoir le contrôle une fois la fonction (procédure) terminée.
Habituellement, la pile est utilisée à cette fin, bien que les langages de programmation ou le développeur lui-même puissent fournir une variété d'options pour transférer le contrôle. La programmation moderne admet que le nom d'une fonction peut être non seulement un paramètre: il peut être formé lors de l'exécution de l'algorithme. Un algorithme peut également être créé lors de l'exécution d'un autre algorithme.
Le concept d'algorithmes récursifs, lorsque leurs noms et leurs corps peuvent être déterminés au moment de la formation de la tâche (choix de l'algorithme souhaité), étend la récursivité non seulement à la façon de faire quelque chose, mais aussi à qui exactement devrait fais-le. Choisir un algorithme par son nom "qui a du sens" est prometteur, mais crée des difficultés.
Récursivité sur un ensemble de fonctions
On ne peut pas dire qu'un algorithme est récursif lorsqu'il s'appelle lui-même et c'est tout. La programmation n'est pas un dogme, et le concept de récursivité n'est pas une exigence exclusive pour vous appeler à partir du corps de votre propre algorithme.
Les applications pratiques ne donnent pas toujours une solution propre. Souvent, les données initiales doivent être préparées, et le résultat de l'appel récursif doit être analysé dans le contexte de l'ensemble du problème (l'ensemble de l'algorithme) dansdans l'ensemble.
En fait, non seulement avant qu'une fonction récursive soit appelée, mais aussi après qu'elle soit terminée, un autre programme peut ou doit être appelé. S'il n'y a pas de problème particulier avec l'appel: la fonction récursive A() appelle la fonction B(), qui fait quelque chose et appelle A(), alors immédiatement il y a un problème avec le retour de contrôle. Après avoir terminé l'appel récursif, la fonction A() doit recevoir le contrôle afin de rappeler B(), qui l'appellera à nouveau. Rendre le contrôle dans l'ordre sur la pile à B() est la mauvaise solution.
Le programmeur n'est pas limité dans le choix des paramètres et peut les compléter avec des noms de fonctions. En d'autres termes, la solution idéale est de passer le nom de B() à A() et de laisser A() lui-même appeler B(). Dans ce cas, il n'y aura aucun problème avec le retour du contrôle, et la mise en œuvre de l'algorithme récursif sera plus transparente.
Compréhension et niveau de récursivité
Le problème avec le développement d'algorithmes récursifs est que vous devez comprendre la dynamique du processus. Lors de l'utilisation de la récursivité dans les méthodes objet, en particulier au niveau d'un ancêtre abstrait, il y a un problème de compréhension de votre propre algorithme dans le contexte de son temps d'exécution.
Actuellement, il n'y a pas de restrictions sur le niveau d'imbrication des fonctions et la capacité de la pile dans les mécanismes d'appel, mais il y a un problème de compréhension: à quel moment quel niveau de données ou quelle place dans l'algorithme général appelé le récursif fonction et sur quel nombre d'appels elle est elle-même.
Les outils de débogage existants sont souvent impuissantsindiquez au programmeur la bonne solution.
Boucles et récursivité
On considère que l'exécution cyclique est équivalente à la récursivité. En effet, dans certains cas, l'algorithme récursif peut être implémenté dans la syntaxe des constructions conditionnelles et cycliques.
Cependant, s'il est clairement entendu qu'une fonction particulière doit être implémentée via un algorithme récursif, toute utilisation externe d'une boucle ou d'instructions conditionnelles doit être abandonnée.
Le sens ici est qu'une solution récursive sous la forme d'une fonction s'utilisant elle-même sera un algorithme complet, fonctionnellement complet. Cet algorithme demandera au programmeur de le créer avec effort, en comprenant la dynamique de l'algorithme, mais ce sera la solution finale qui ne nécessite pas de contrôle externe.
Toute combinaison d'opérateurs externes conditionnels et cycliques ne nous permettra pas de représenter l'algorithme récursif comme une fonction complète.
Consensus de récursivité et POO
Dans presque toutes les variantes de développement d'un algorithme récursif, un plan se pose pour développer deux algorithmes. Le premier algorithme génère une liste d'objets futurs (instances), et le second algorithme est en fait une fonction récursive.
La meilleure solution serait d'organiser la récursivité comme une seule propriété (méthode) qui contient réellement l'algorithme récursif, et de mettre tout le travail préparatoire dans le constructeur d'objet.
Un algorithme récursif ne sera la bonne solution que s'il fonctionneseul, sans contrôle ni gestion externe. Un algorithme externe ne peut que donner un signal pour fonctionner. Le résultat de ce travail devrait être la solution attendue, sans support extérieur.
La récursivité devrait toujours être une solution autonome complète.
Compréhension intuitive et complétude fonctionnelle
Lorsque la programmation orientée objet est devenue la norme de facto, il est devenu évident que pour coder efficacement, vous devez changer votre propre façon de penser. Le programmeur doit passer de la syntaxe et de la sémantique du langage à la dynamique de la sémantique lors de l'exécution de l'algorithme.
Caractéristique de la récursivité: elle peut s'appliquer à tout:
- grattage Web;
- opérations de recherche;
- analyse des informations textuelles;
- lire ou créer des documents MS Word;
- échantillonner ou analyser des balises…
Caractéristique de la POO: elle permet de décrire un algorithme récursif au niveau d'un ancêtre abstrait, mais prévoit qu'il se réfère à des descendants uniques, chacun ayant sa propre palette de données et de propriétés.
La récursivité est idéale car elle nécessite la complétude fonctionnelle de son algorithme. La POO améliore les performances d'un algorithme récursif en lui donnant accès à tous les enfants uniques.
