Une procédure récursive est une procédure récursive. Une définition plus sérieuse Une procédure récursive est une procédure qui sappelle elle-même. La récursivité est un domaine très intéressant de linformatique, un peu abstrait, mais très élégant; elle permet de résoudre certains problèmes dune manière très rapide, alors que si on devait les résoudre de manière itérative, il nous faudrait beaucoup plus de temps et de structures de données intermédiaires. La récursivité utilise toujours la pile du programme en cours. On appelle pile une zone mémoire réservée à chaque programme; sa taille peut être fixée manuellement par lutilisateur. Son rôle est de stocker les variables locales et les paramètres dune procédure. Supposons que nous sommes dans une procédure proc1 dans laquelle nous avons des variables locales. Ensuite nous faisons appel à une procédure proc2; comme le microprocesseur va commencer à exécuter proc2 mais quensuite il reviendra continuer lexécution de proc1, il faut bien stocker quelque part les variables de la procédure en cours proc1; cest le rôle de la pile. Tout ceci est géré de façon transparente pour lutilisateur. Dans une procédure récursive, toutes les variables locales sont stockées dans la pile, et empilées autant de fois quil y a dappels récursifs. Donc la pile se remplit progressivement, et si on ne fait pas attention on arrive à un débordement de pile. Ensuite, les variables sont désempilées (et on dit désempilées, pas dépilées). Dans ce qui suit, nous allons utiliser le terme procédure pour désigner aussi bien une procédure quune fonction. Une procédure récursive comporte un appel à elle-même, alors quune procédure non récursive ne comporte que des appels à dautres procédures. Toute procédure récursive comporte une instruction (ou un bloc dinstructions) nommée point terminal ou point dappui ou point darrêt, qui indique que le reste des instructions ne doit plus être exécuté. Exemple : procedure recursive(paramètres); // déclaration des variables locales begin if TEST_DARRET then begin instructions du point darrêt end else //----- exécution begin instructions; recursive(paramètres changés); // appel récursif instructions; end; end; On constate, et il le faut, que les paramètres de lappel récursif changent; en effet, à chaque appel, lordinateur stocke dans la pile les variables locales; le fait de ne rien changer dans les paramètres ferait que lordinateur effectuerait un appel infini à cette procédure, ce qui se traduirait en réalité par un débordement de pile, et darrêt de lexécution de la procédure en cours. Grâce à ces changements, tôt ou tard lordinateur rencontrera un ensemble de paramètres vérifiant le test darrêt, et donc à ce moment la procédure récursive aura atteint le fond (point terminal). Ensuite les paramètres ainsi que les variables locales sont désempilées au fur et à mesure quon remonte les niveaux. Nous allons étudier en détail maintenant le mécanisme de la récursivité sur un exemple concret, la combinaison des lettres dune chaîne de caractères (ou anagrammes). La réalisation de la procédure récursive faisant cela sera étudiée plus loin, nous allons décrire ici le mécanisme interne et le stockage des paramètres et des variables locales. procedure combinaison2(st, tete: string); var i: integer; begin if length(st) = 1 then memo1.lines.add(tete + st) else for i := 1 to length(st) do begin combinaison1(copy(st, 2, length(st) - 1), tete + st[1]); st := copy(st, 2, length(st) - 1) + st[1]; end; end;
Posted on: Sat, 23 Nov 2013 20:55:18 +0000
Trending Topics
Recently Viewed Topics
© 2015