Deug Mias-2, 2000-2001
Informatique
Institut Galilée

TD-3
Différents aspects de la récursivité

I. Récursivité et décidabilité.
L’une des principales difficultés d’un programme récursif est de prédire s’il va bien faire ce que vous pens(i)ez. Non seulement on peut facilement dépasser les capacités de la machine en mémoire (et notamment dépasser quantité de mémoire allouée à la pile), mais surtout, il est aisé d’écrire des programmes qui ne terminent jamais.

On pourrait rêver d’un langage dont le compilateur testerait si votre programme est “ bien construit ” (c’est-à-dire, s’il termine) et le cas échéant, vous avertisse du problème.
Malheureusement, dès lors que l’on a un programme avec la structure “ while ” (ou de façon équivalente “ repeat until ” ou encore les “ goto ”), ce n’est pas possible, comme nous le montrons dans l’exercice suivant.

Exercice 1. Indécidabilité du problème de l'arrêt.

Pour un programme donné, de deux choses l'une soit il  s'arrête au bout d'un certain temps (en renvoyant la valeur attendue ou encore en renvoyant une erreur)
soit il ne s'arrête jamais (il " boucle ", il " tourne en rond ", fait une infinité de calculs, etc.).

Maintenant, vous construisez le programme que vous voulez,  et vous le montrez à Dieu en lui demandant s'il peut deviner si votre programme va s'arrêter un jour ou non. Dieu a beau avoir tout son temps et être omniscient, nous allons prouver qu'il existe au moins un programme pour lequel il ne saura pas répondre à la question !
Autrement dit, il n'existe pas d'algorithme (appelons-le " VaStopper ")  qui prenne en entrée un programme et qui réponde vrai si “ ce programme va stopper un jour ”  et faux sinon.

Exemples :
VaStopper( var i ; Begin i :=i+1 end.) = vrai
VaStopper( Begin while true do End.) = faux

1. Prouvez que VAStopper n’existe pas.
    Indication. Faire une preuve par l'absurde : supposez qu'il existe, qu'en déduisez-vous ?

Exercice 2. La fonction d’Ackermann 
Elle est définie par les relations	A(0,m)=2m	A(n,0)=1 	et 	A(n,m)=A(n-1,A(n,m-1)).
Elle a la particularité d’être primitive mais pas primitive récursive (cela se montre en prouvant qu’elle “ croît ” beaucoup plus vite que n’importe quelle fonction primitive récursive), cela signifie qu’on ne peut pas la calculer dans un langage qui n’aurait que des boucles for, des tests booléens, les opérations arithmétiques de bases : on a besoin du  “ while ” ou d’un programme récursif.

1.	Montrer que les relations ci-dessus définissent bien, de façon unique,  une fonction.
(i.e., pour tout couple (m,n), les calculent terminent).
2.	Calculer A(1,2), puis A(2,1), puis A(2,2), puis A(2,3), puis A(3,2), puis A(4,4).

II. Récursivité et complexité

Exercice 3. La suite de Fibonacci 
fn+2 = fn+1+fn  (avec les conditions initiales f 0 = 1 et f1 = 1) a été introduite par Léonard de Pise (alias Bonacci fils, alias Fibonacci) lors de l 'étude d'une évolution d'une population de lapin.

Function fib(n :integer) :integer
Begin
if (n=0) or (n=1) then fib :=1 
else fib :=fib(n-1)+fib(n-2)
End ;

1.	Tracer l’arbre de calcul de Fib(5) pour le programme ci-dessus (comme fait en cours).
2.	Comment le programme va-t-il “ parcourir ” cet arbre ? 
3.	Comment le programme (avec la modification fib :=fib(n-2)+fib(n-1)) parcourt-il cet arbre ?
4.	Quel est l’ordre de grandeur de la taille de l’arbre associé au calcul de Fib(n) ?
5.	Est-il possible de calculer f999  avec au plus 60 additions et 120 multiplications (au lieu de 999 additions) ?

Exercice 4. L’algorithme de tri rapide (Quick Sort)

Il s’agit d’un algorithme de tri révolutionnaire, inventé par C.A.R. Hoare en 1962.

1. Expliquez “ grosso modo ” comment il fonctionne.

Program TriRapide;
Uses Crt;
CONST n=10;

VAR
T:array[1..n] of integer;
i:byte;

Procedure QuickSort(g,d:integer);
var p,w,i,j:integer;
Begin
if d-g>0 
 then begin
    p:=T[d];i:=g-1;j:=d;
      repeat
repeat i:=i+1 until T[i]>=p;
repeat j:=j-1 until T[j]<=p;
w:=T[i];T[i]:=T[j];T[j]:=w;
       until j<=i; 
    T[j]:=T[i];T[i]:=T[d];T[d]:=w;
   QuickSort(g,i-1);
   QuickSort(i+1,d); 
 end;
End;

BEGIN
for i:=1 to n do readln(T[i],' ');
Quicksort(1,10);
for i:=1 to n do write(T[i],' ');
END.

III. Récursivité et logique

Exercice 5. Le paradoxe de Russell

Un certain nombre de définitions récursives peuvent déboucher sur des cercles vicieux. Ce problème est connu depuis l’Antiquité (Epiménide, un crétois, affirmait “ Tous les Crétois sont des menteurs. ” ce qui bien sûr aboutit à un paradoxe : Epiménide dit-il la vérité ou pas ?). Ce n’est qu’avec le fondement théorique des mathématiques au début du siècle (Hilbert, Russell, axiomatique de Zermelo-Fraenkel ) que l’on a su expliquer divers paradoxes. La plupart reposent sur le fait suivant, appelé “ paradoxe de Russell ” : l’ensemble de tous les ensembles n’est pas un ensemble. 

1. Prouvez que “ L’ensemble de tous les ensembles n’est pas un ensemble. ” 

2. Il y a à Villetaneuse un barbier qui rase tous les habitants qui ne se rasent pas eux-mêmes (et seulement ceux-ci). Que pouvez-vous dire de ce barbier ?

Deug Mias-2, 2000-2001
Informatique
Institut Galilée
TP-3
Différents aspects de la récursivité

I. Récursivité et décidabilité.

Nous avons vu dans l’exercice 1 du TD  3 qu’il existait au moins au programme pour lequel on ne sait pas prédire s’il va s’arrêter à tous les coups ou non. 

Le programme suivant montre que même pour des programmes très simples, la question de l’arrêt n’est en effet pas évidente.

Exercice 1.  Le problème 3x+1
Soit x un entier positif. Tant que x  est différent de 1, si x est pair, alors on le divise par deux et s’il est impair on le multiplie par trois et on ajoute un.

Implantez ce programme en affichant les transformations successives de x et vérifiez ce qui se passe pour un certain de nombre de valeurs. Que conjecturez-vous ?

Exercice 2.  La fonction d’Ackermann

Implanter la fonction d’Ackermann et vérifier les valeurs calculées en TD. En calculer d’autres.

II. Récursivité et complexité

Exercice 3. La suite de Fibonacci 

Pour les exercices suivants, Borland Pascal sous Windows n’est pas suffisant car on ne peut y suivre l’évolution de la pile. Allez sous MS-DOS, placez-vous sous votre répertoire personnel (tapez “ cd z:\monNom\ ”)  puis lancez Turbo-Pascal (tapez “ turbo ”).

Faire un programme qui calcule récursivement la suite de Fibonacci.
Tracer l’évolution de la pile lors du calcul de Fib(5)

Appuyez sur contrôle-F3 (pour faire apparaître la pile “ stack ”) puis appuyez sur F7 pour exécuter votre programme pas à pas.
Observez l’évolution de la pile et comparez avec ce que vous avez fait en TD.

Lancer Maple et rentrer le programme suivant (besoin d’aucune connaissance si ce n’est que shift-Entrée passe à la ligne suivante et que la touche entrée seule lance le calcul. En ce qui concerne la syntaxe, elle est facile : “ od ” ferme un “ do ”, “ fi ” ferme un “ if ”, etc.)

> fib:=proc(n)
option remember; 
if (n=0) or (n=1) then RETURN(1)
else RETURN(fib(n-1)+fib(n-2))
fi end;

Demandez
> fib(24);
et
> fib(1000);

Enlever le “ option remember ” 
> fib:=proc(n)
if (n=0) or (n=1) then RETURN(1)
else RETURN(fib(n-1)+fib(n-2))
fi end;

et redemandez 
> fib(24);
Que constatez-vous ? Quelle est votre explication ?

Exercice 4. QuickSort 

Implantez l’algorithme TriRapide vu en TD mais avec la modification suivante :
Procedure QuickSort(g,d:integer, var T:array[1..n] of integer);

Appuyez sur contrôle-F3 (pour faire apparaître la pile “ stack ”) puis appuyez sur F7 pour exécuter votre programme pas à pas pour la suite suivante 3,4,5,1,6,7,10,9,8,2.
Tracez (sur votre cahier !) l’arbre correspondant.

Remarque : un futur TD montrera que QuickSort est bien un tri rapide (en fait, le plus rapide de tous en un certain sens) : pour trier n nombres, QuickSort n’utilise en général que n ln n opérations alors que les autres méthodes en utilisent souvent n2.