Récursivité

GW-Basic, utilisé par PC-Basic

Programme avec Texte Seulement
PC-BASIC

En mathématiques, une fonction récursive est une fonction qui s'appelle elle-même ; la sortie passée devient l'entrée actuelle, à l'infini.

En matière de programmation informatique, la définition d'une fonction récursive est similaire : c'est une procédure ou une sous-routine qui s'appelle elle-même.

Comme l'enseignant et auteur Charles E. Cook l'a observé de manière ludique:

"Cela semble d'abord très déconcertant... un peu comme un serpent qui avale sa propre queue. Le serpent finirait-il par disparaître ?"

L'idée d'un sous-programme récursif est généralement présentée aux étudiants en informatique grâce à une factorielle (représentée par le caractère !, brièvement expliqué dans la section Algorithme de permutation de Heap).

Par exemple, 6! (lu comme "six factoriel") est égal à 720.

Considérez comment nous pourrions écrire un programme GW-BASIC pour évaluer les factoriels : certainement une boucle semble nécessaire ainsi qu'une variable gardant une trace du produit final toujours croissant. Peut-être que le programme qui serait de nature itérative, plutôt que récursive, pourrait ressembler à ceci :

5 REM FACT.BAS
10 KEY OFF:CLS
20 INPUT "Input n, output will be n!. what is your n";N
30 IF N=0 THEN PRINT"1":END
40 IF N<0 THEN 20
50 FOR X=N-1 TO 1 STEP -1
60 N=N*X
70 NEXT X
80 PRINT N
90 END

Si votre entrée est 6, la sortie sera 720, exactement ce à quoi vous vous attendez.

Mais les factorielles se prêtent aux routines récursives car la sortie suivante dépend toujours de l'entrée précédente.

 Le langage de programmation Java autorise les routines récursives ; considérez le programme Java ci-dessous, qui a une méthode factuelle (elle est encadrée) qui s'appelle de manière répétée jusqu'à ce que la variable n se termine à zéro (à ce point, 1 est renvoyé à la méthode principale) :

//recursive factorial program

import java.util.Scanner;

public class Factorial {

        public static void main(String[] args) {

        Sc anner input = new Scanner (System.in);

        System.ouf.print("lnput n, output will be n!. What is your n?");

        int n = input.nextlnt();

int result = facf(n);

System. out. print(result);

input.close();

}

public static int fact(int n) {

      if (n == 0)
       return 1;

      else
         return n*facf(n-1); }

}

L'astuce réside dans la seconde instruction retun : return n*fact(n-1) ; puisque la méthode prend la valeur "actuelle" de n et la multiplie par le résultat de la méthode factuelle - après que cette méthode a reçu une valeur de paramètre inférieure à n.

De plus, le fait que la variable entière primitive n soit locale et non globale - avec des instances répétées de la variable créées à chaque passage dans la méthode - facilite également la récursivité (rappelons que toutes les variables en GW-BASIC sont globales).

Remarquez comment le sous-programme évite la structure itérative du programme FACT.BAS : il n'y a pas de boucles while et pas de boucles for (et, évidemment, pas d'instruction GOTO). L'algorithme récursif ressemble en effet à un serpent qui avale sa propre queue.

Au fait : réécrivez la méthode fact de la manière suivante, et le compilateur lèvera une exception (ce qui signifie, dans ce cas, que le programme se terminera sans produire de résultat) :

public static intfact(int n) {
     return n*facf(n-1);

La condition de retour "limite" - que faire lorsque n atteint 0 - est nécessaire car elle empêche une valeur de n décroissante. Chaque routine récursive doit avoir au moins une condition d'omission (également appelée condition de terminaison ou cas de base).

GW-BASIC ne permettra pas à une fonction, qui est l'équivalent approximatif d'une méthode Java, d'être définie fonctionnellement de manière récursive. (Fait intéressant, BASIC a évolué : Visual Basic autorise les fonctions définies de manière récursive.)

Pour comprendre pourquoi, essayez d'exécuter le programme suivant.

5 REM FACTR1
10 KEY OFF:CLS
20 DEF FNFAC(X)=X*FNFAC(X-1)
30PRINT FNFAC(6)

Bien qu'il serait agréable de voir une sortie à 720, tout ce qui vous est présenté à la place est

Out of memory in 30.

Après avoir configuré la fonction de manière récursive, il n'y a aucun moyen d'empêcher n de voyager dans le terrier du lapin - il n'y a malheureusement aucun moyen de configurer une condition limite, puisque GW-BASIC limite une définition de fonction à une affectation à une seule ligne.

Quels que soient vos efforts, une fonction stylisée de manière récursive utilisant l'instruction DEF FN aboutira finalement à une boucle infinie, provoquant la chute du programme à travers une trappe récursive.

Ainsi, au lieu d'essayer sans succès d'utiliser l'instruction DEF FN, travaillons avec GOSUB pour construire une sous-routine de style récursif pour calculer les factorielles.

Parce que notre sous-programme récursif ne sera pas complètement exempt des constructions de boucle standard trouvées dans le code itératif (bien qu'il s'en approchera assez), nous considérerons le programme FACTR2.BAS ci-dessous pseudo-récursif.

Mais nous devons être prudents. Dans un numéro de juillet 1982* de Compute! (Numéro 26. À une époque singulière de l'histoire de l'informatique où les périodiques imprimaient en fait des listes de codes), magazine détaillant le code BASIC pour programmer une solution récursive au puzzle des tours de Brahma (Hanoi), l'auteur Earl Wuchter explique comment l'arrangement basé sur la pile des instructions RETURN - c'est-à-dire dernier entré, premier sorti (LIFO) - peut entraîner des complications importantes :

"L'ordinateur doit être capable de se souvenir des "adresses de retour" __ Donc, avant GOSUBbing, "l'adresse" à
RETURN est mis sur la pile de l'ordinateur et ensuite retiré de la pile par RETURN.

Il y a une limite au nombre d'adresses de retour qui peuvent être poussées sur la pile. Ce n'est normalement pas un problème puisque la plupart des sous-programmes reviennent directement via RETURN, soulageant la pile du numéro d'adresse. Les sous-programmes récursifs et auto-appelants, cependant, ne sont pas RETURNING.

C'est GOSUB-G0SUB-GOSUB, etc. Sauf si la récursivité est soigneusement gérée, la pile pourrait rapidement se remplir d'adresses de retour et on dit alors qu'elle déborde."

Alors assurons-nous de ne pas provoquer de débordement dans notre programme FACTR2.BAS.

Il est assez clair que FACTR2.BAS est un peu un tricheur : le 0! et 1! les cas sont éliminés immédiatement sans même entrer dans le sous-programme récursif.

Mais, entrée en 6 comme votre N, et, en effet, la sortie sera 720 calculé après que le sous-programme se soit appelé plusieurs fois. Malheureusement, le programme a besoin de plusieurs compteurs pour arriver à la réponse finale.

5 REM FACTR2.BAS
10 CLS:KEY OFF
20 INPUT "Input n, output will be n!. what is your n";N
22 IF N<0 THEN 20
24 IF N=0 THEN PRINT "1":END
26 IF N=1 THEN PRINT "1":END
30 Y=N-1
40 N=N*Y
50 Y=Y-1
60 IF Y>0 THEN GOSUB 40 ELSE 80
70 RETURN
80 PRINT N
90 END

Il est théoriquement possible de transformer n'importe quel programme d'une structure itérative en une structure récursive. En fait, si les langages populaires comme BASIC ne s'en tiennent pas très tôt à l'approche itérative, la valeur par défaut aujourd'hui pourrait être la récursivité.

Les langages de programmation comme Java qui autorisent les variables locales autorisent également de véritables sous-programmes récursifs, mais, comme il n'y a pas une quantité infinie d'espace réservé aux variables locales, méfiez-vous : votre programme se terminera si vous créez trop de variables locales ou si vous renoncez à limiter conditions.
Avec quelques truquages de jury, nous avons pu écrire un sous-programme factoriel pseudo-récursif dans GW-BASIC. Mais pour avoir une chance de vraiment tester vos côtelettes récursives, essayez de réécrire le programme d'algorithme de Heap HEAP. BAS récursivement.
Mieux encore, essayez d'écrire du code récursif pour la routine de tri rapide. Rappelons que, dans les chapitres précédents, nous avons détaillé comment le tri à bulles et le tri par sélection ne sont pas tout à fait à la hauteur en termes de vitesse lorsqu'il s'agit d'arranger de grandes listes d'éléments. Mais le tri rapide porte bien son nom : c'est l'une des approches les plus rapides pour commander des articles. [En moyenne, la complexité temporelle de l'algorithme de tri rapide est O(n log n).]

Le tri rapide utilise une approche appelée diviser pour mieux régner. La list non trié est divisé en deux partitions ; le point de rupture entre eux s'appelle le pivot. Certains codeurs définissent le pivot comme étant la première valeur de la liste ; d'autres, la dernière valeur.

Plus communément, cependant, le pivot est défini sur l'élément du milieu de la liste non trié.

À partir de là, les éléments sont échangés de chaque côté du pivot, ce qui fait que la partition de gauche (sous le pivot) contient tous les éléments inférieurs au pivot, et la partition de droite (au-dessus du pivot) contient tous les éléments supérieurs au pivot - avec le pivoter bien au milieu.

La récursivité entre en jeu à ce stade : répétez de manière récursive cette routine de tri rapide sur chaque partition jusqu'à ce que la liste complète des éléments soit triée par ordre croissant.

Vous trouverez ci-dessous le code GW-BASIC pour effectuer uniquement le premier ensemble de swaps de chaque partition ; le pivot a été défini sur le premier élément de la liste non ordonnée.

QUICK.BAS vous permet de parcourir chaque itération, en codant par couleur les éléments de la liste pour la compréhension (appuyez simplement sur Entrée pour déplacer vers l'avant).

Il devrait cependant vous apparaître immédiatement que le programme n'est pas de nature récursive ; réécriture QUICK.BAS non seulement pour trier rapidement les éléments, mais aussi pour le faire de manière récursive devrait vous occuper pendant des heures.

Pour vous aider à réécrire le programme GW-BASIC de manière récursive (ou au moins pseudo-récursive), jetez un œil à la routine récursive Java suivante pour le processus de tri rapide. Juste comme QUICK.BAS, le pivot est réglé sur la première valeur. Examinez attentivement la méthode de tri, qui s'appelle elle-même.

//quicksort Java program

lmport java.util.Scanner;

public class QuickSort {

public static void main(String[] args) {

Scanner input = new Scanner(System./n);

System.ouf.print("How many items to (quick) sort?");

lnt totalltems = input.nextlnt();

int[] a = new int[totalltems];

int entry = 0;

//gather each item from the user:

for(int count = 0; count < totalltems; count++) {

      System.out.print("Enter in element #" + count + ...,.);

      entry = input.nextlnt(); a[count] = entry;

}

//submit the array for (quick) sorting:

int lowlndex = 0;

int highlndex = a.length -1;

sort{a, lowlndex, highlndex);

//call the sort method

//output the (quick) sorted array, using an //enhanced for loop:

for (int i: a)

      System.ouf.print(i +",");

      input.close(); //close Scanner

}

public static void sort(int[] a, int lowlndex, inthighlndex) {

if (lowlndex >= highlndex ) return;

      intx = lowlndex; int y = highlndex;

      int pivot = a[lowlndex];

     //pivot value set to first
        //item in array

     while (x < y) {

        while (a[x] < pivot) {
           x++;

    } 

          while (a[y] > pivot) {
            y-;

        }

     If (x <= y) {

         int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
        x++;
        y-;

      }

   }

   //recursive sort: sort(a, lowlndex, y);

     sort(a, x, highlndex);

    }

}

Si seulement GW-BASIC vous permettait de définir des fonctions de manière récursive (et plus étendue), toutes ces complications frustrantes pourraient être évitées.

Là encore, si nous pouvions en quelque sorte changer GW-BASIC pour permettre la récursivité des fonctions, ce ne serait plus le GW-BASIC que nous connaissons et aimons - et est-ce vraiment ce que nous voulons ?

5 REM QUICK,BAS
10 KEY OFF:CLS:COLOR 15
15 DIM ARRAY(50)
16 ELEM=1:I=0
20 PRINT "--- QUICKSORT : UNE ITÉRATION DE DIVISER POUR RÉGNER ---"
30 PRINT
40 PRINT "Entrez votre tableau, un nombre à la fois. Entrez un nombre négatif pour terminer."
50 PRINT "Il y a un maximum de 50 éléments autorisés."
60 WHILE I>=0
70 PRINT "Élément #";ELEM;":";
80 INPUT I:ARRAY(ELEM)=I
90 ELEM=ELEM+1
100 IF ELEM>50 THEN I=-1
120 WEND
130 ELEM=ELEM-2 'Obtient le nombre total d'éléments du tableau
200 'Implémente l'algorithme Quicksort
210 PIVOT=ARRAY(1) 'Définit la valeur "pivot" comme premier élément du tableau (mais cela peut être n'importe où)
220 X=2:Y=ELEM 'Définit les éléments initiaux à gauche et à droite pour les scans
240 'Scanne de gauche à droite pour trouver une valeur supérieure au pivot
250 WHILE ARRAY(X)<PIVOT
260 X=X+1
265 IF X>=Y THEN GOTO 290
267 GOSUB 500
270 WEND
275 'Ensuite, balaye de droite à gauche pour trouver une valeur inférieure au pivot
280 WHILE ARRAY(Y)>PIVOT
282 Y=Y-1
283 IF X>=Y THEN GOTO 290
284 GOSUB 500
285 WEND
290 'Tout d'abord, vérifie si X=Y ; si c'est le cas, échange la valeur médiane avec le pivot et termine le programme
300 IF X>=Y THEN GOTO 400
310 'Si X n'est pas égal à Y, échange ARRAY(X) avec ARRAY(Y) et continue à scanner
320 TEMP=ARRAY(X):ARRAY(X)=ARRAY(Y):ARRAY(Y)=TEMP
325 GOSUB 500
330 GOTO 240
400 'Échange la valeur médiane avec le pivot, imprime le tableau trié et termine le programme
405 IF ARRAY(X)<PIVOT THEN GOTO 415
410 TEMP=ARRAY(X):ARRAY(X)=PIVOT:ARRAY(1)=TEMP
415 PRINT:PRINT "Le tableau Quicksort(ed) est:"
416 'Corrige l'échange élément 1/élément 2
417 TEMP=ARRAY(1):ARRAY(1)=ARRAY(2):ARRAY(2)=TEMP
420 FOR A=1 TO ELEM
430 PRINT ARRAY(A);" ,";
440 NEXT A
450 END
500 'Imprime le tableau, jusqu'à présent (avec surbrillance jaune de l'analyse de l'élément actuel et pivot en rouge)
510 COLOR 4
520 PRINT ARRAY(1);" "; 'Le pivot
530 FOR A=2 TO ELEM
540 COLOR 15
550 IF A=X OR A=Y THEN COLOR 14
560 PRINT ARRAY(A);" ";
570 NEXT A
580 LINE INPUT L$
590 RETURN