Apprendre la récursivité avec Xcas Renée De Graeve

Table des matières

• Chapitre 1  Un programme itératif et sa version récursive
  • 1.1  Programme avec 1 seul appel récursif
    • 1.1.1  Exemple1 : traduction d’un pour avec 1 appel récursif
    • 1.1.2  Exemple2 : traduction d’un tantque
    • 1.1.3   Exercice1
  • 1.2  Le test d’arrêt
• Chapitre 2  Programmes avec plusieurs appels récursifs
  • 2.1  Programme avec 2 appels récursifs
  • 2.2  Programme avec 3 appels récursifs
• Chapitre 3  Solution des exercices et des programmes réalisant les télés
  • 3.1  Solution des exercices en syntaxe Xcas
  • 3.2  Solution des exercices en syntaxe Python
  • 3.3  Les programmes des télés en syntaxe Xcas
  • 3.4  Les programmes des télés en syntaxe Python

Index

Avant-propos

On a choisit ici de faire des programmes récursifs graphiques : lorsqu’ un dessin est récursif on peut facilement voir dans ce dessin le même dessin en plus petit et donc la récursivité se voit.
Comme exemple d’image récursive, on peut prendre un écran de télévision sur lequel il y a un présentateur et une télévision qui diffuse la même chaîne et sur cette télévision on peut voir un présentateur et une télévision qui diffuse la même chaîne ou une chaîne différente etc...
Il peut aussi y avoir un présentateur et plusieurs télévisions qui diffusent la même chaîne ou des chaîne différentes...
Dans les exemples qui suivent on a :
avec tele1 on voit le présentateur de tele1 et l’écran de tele1,
avec tele2 on voit le présentateur de tele2 et l’écran de tele2,
avec tele12 on voit le présentateur de tele1 et l’écran de tele21,
avec tele21 on voit le présentateur de tele2 et l’écran de tele12.

python_compat(0)

okonload

axes=0;tele1(0,0,120,6) ok

axes=0;tele2(0,0,120,6) ok

axes=0;tele12(0,0,120,6) ok

axes=0;tele21(0,0,120,6) ok

les programmes des solutions des exercices ainsi que ceux permettant de réaliser les télés sont a la fin du document dans le chapitre 3.

Chapitre 1  Un programme itératif et sa version récursive

1.1  Programme avec 1 seul appel récursif

1.1.1  Exemple1 : traduction d’un pour avec 1 appel récursif

On veut tracer une suite de $n$ cercles de centre et de rayon successivement $z0,r$ $z0+3*r/2,r/2$.. $z0+r+r/2+..r/2^2,r/2^n$.
On a écrit un programme graphique itératif cerclesp(z0,r,n) qui utilise pour cela l’instruction pour k de 1 jusque n faire...fpour et une séquence L qui va contenir la suite des instuctions graphiques à exécuter.
En mode Xcas

cerclesp(z0,r,n):={
local L,k;
L:=NULL;
pour k de 1 jusque n faire 
   L:=L,cercle(z0,r);
   z0:=z0+3*r/2;
   r:=r/2;
fpour;
return L;
}:;

okonload
On peut aussi utiliser une liste L qui va contenir la suite des instuctions graphiques à exécuter.
Pour cela on utilise la commande append pour ajouter un élément à la liste L soit avec l’instruction :
L:=append(L,cercle(z0,r)); soit avec l’instruction :
L.append(cercle(z0,r));

cerclesp(z0,r,n):={
local L,k;
L:=[];
pour k de 1 jusque n faire 
   L.append(cercle(z0,r));
   z0:=z0+3*r/2;
   r:=r/2;
fpour;
return L;
}:;

okonload
On peut traduire ce programme en Python en tapant python(cerclesp).

def cerclesp(z0,r,n):
    # local L,k
    L=[]
    for k in range(1,n+1):
        L=append(L,cercle(z0,r))
        z0=z0+3*r/2
        r=r/2
    return(L)

okonload
On tape, si on veut voir les axes :
cerclesp(0,80,6) ok

ou bien si on ne veut pas voir les axes :
axes=0;cerclesp(0,80,6) ok

Pour écrire la version récursive de ce programme il faut voir le dessin, de paramètres z0,r,n, comme étant composé :
d’un grand cercle de centre z0 et de rayon r et du même dessin de paramètres z0+3*r/2,r/2,n-1.
Pour que ceci soit correct, il faut bien sûr prévoir un test sur n : par exemple si n>0 alors ....fsi;
On écrit la procédure récursive cerclesr1(z0,r,n) et on tape :

cerclesr0(z0,r,n):={
local L;
L:=NULL;
si n>0 alors 
 L:=L,cercle(z0,r);
 L:=L,cerclesr1(z0+3*r/2,r/2,n-1);
fsi;
retourne L;
}:;

okonload
ou plus simplement sans utiliser de variables locales :

cerclesr1(z0,r,n):={
si n>0 alors 
  retourne cercle(z0,r),cerclesr1(z0+3*r/2,r/2,n-1);
fsi;
retourne NULL;
}:;

okonload
ou bien on utilise comme test d’arrêt si n<=0 alors retourne NULL; fsi;

cerclesr2(z0,r,n):={
si n<=0 alors 
   retourne NULL; 
fsi;
retourne cercle(z0,r),cerclesr2(z0+3*r/2,r/2,n-1);
}:;

okonload
ou en syntaxe Python

def cerclesr0(z0,r,n) :
    #local L
    L=NULL
    if n>0 :
       L=L,cercle(z0,r),cerclesr2(z0+3*r/2,r/2,n-1)
    return(L)

okonload

def cerclesr1(z0,r,n) :
    if n>0 :
       return(cercle(z0,r),cerclesr2(z0+3*r/2,r/2,n-1))
    return(NULL)

okonload

def cerclesr2(z0,r,n):
   if n<=0 :
       return(NULL)
   return(cercle(z0,r),cerclesr2(z0+3*r/2,r/2,n-1))

okonload
cerclesr1(0,80,6) ok

cerclesr2(0,80,4) ok

1.1.2  Exemple2 : traduction d’un tantque

On peut vouloir faire un dessin similaire composé d’un certain nombre de cercles avec comme condition d’arrêt : le rayon des cercles doit être supérieur ou égal, par exemple, à 2.
On écrit alors un programme itératif qui utilise l’instruction tantque ...faire ...ftantque et soit une séquence, soit une liste L

cerclest(z0,r):={
local L;
L:=[];
tantque r>=2 faire 
 L.append(cercle(z0,r));
 z0:=z0+3*r/2;
 r:=r/2;
ftantque;
retourne L;
}:;

okonload
ou en langage Python

def cerclest(z0,r):
    # local L
    L=[]
    while r>=2 :        
        L.(append(cercle(z0,r)))
        z0=z0+3*r/2
        r=r/2
    return(L)

okonload
cerclest(0,80) ok

Pour écrire la version récursive de ce programme il faut voir le dessin (de paramètres (z0,r) avec r>=2) comme étant composé :
d’un cercle de centre z0 et de rayon r>=2 et
du même dessin plus petit (de paramètres (z0+3*r/2,r/2) avec r/2>=2).
Donc, ce qui va changer c’est le test qui portera sur r.

cerclesr3(z0,r):={
local L;
L:=NULL;
si r>=2 alors 
L:=L,cercle(z0,r);
L:=L,cerclesr3(z0+3*r/2,r/2);
fsi;
retourne L;
}:;

okonload
ou bien avec le test d’arrêt si r<2 alors retourne L; fsi;

cerclesr4(z0,r):={
si r<2 alors retourne NULL; fsi;
retourne cercle(z0,r),cerclesr4(z0+3*r/2,r/2);
}:;

okonload
ou en langage Python

def cerclesr4(z0,r) :
    if r<2 :
        return NULL
    return cercle(z0,r),cerclesr4(z0+3*r/2,r/2)

okonload
cerclesr3(0,80) ok

cerclesr4(0,80) ok

1.1.3   Exercice1

Écrire la version récursive du programme itératif suivant :
cerclexo1(z0,t,r,n) où z0 est l’affixe du centre du grand cercle, t l’angle de rotation du dessin final, r est le rayon du grand cercle et n est le nombre de cercles.

cerclexo1(z0,t,r,n):={
local L,k;
L:=NULL;
pour k de 1 jusque n faire 
 L:=L,cercle(z0,r);
 z0:=z0+3*r*exp(i*(t+pi/4))/2;
 t:=t-pi/4;
 r:=r/2;
fpour;
retourne L;
}:;

okonload
cerclexo1(-190,0,80,2),cerclexo1(0,0,80,3),cerclexo1(220,0,80,4) ok

cerclexo1(0,0,80,6) ok

cerclexo1(0,0,80,6),cerclexo1(0,pi/2,80,6) ok

1.2  Le test d’arrêt

On veut maintenant que dans le dernier cercle, il soit inscrit un hexagone rempli de couleur rouge.
Pour cela, il faut écrire une instruction qui trace le cercle et l’hexagone lorsque k=n.

cerclexo1h(z0,t,r,n):={
local L,k;
L:=NULL;
si n<=0 alors retourne L; fsi;
pour k de 1 jusque n-1 faire 
    L:=L,cercle(z0,r);
    z0:=z0+3*r*exp(i*(t+pi/4))/2;
    t:=t-pi/4;
    r:=r/2;
fpour;
L:=L,cercle(z0,r),isopolygone(z0,z0-r,-6,affichage=1+rempli);
retourne L;
}:;

okonload
cerclexo1h(0,0,80,4) ok

cerclexo1h(0,0,80,4),cerclexo1(0,pi/2,80,4) ok

Écrire la version récursive de ce programme itératif.

Chapitre 2  Programmes avec plusieurs appels récursifs

On choisit dans cette section de ne dessiner que des cercles de rayon r>=5.

2.1  Programme avec 2 appels récursifs

Faire le programme cerclexo2r(z0,t,r),qui réalise les dessins qui suivent (z0 est l’affixe du centre du grand cercle, t l’angle de rotation du dessin final, r est le rayon du grand cercle) :
cerclexo2r(0,0,40) ok

cerclexo2r(0,0,80) ok

2.2  Programme avec 3 appels récursifs

Faire le programme cerclexo3r(z0,t,r) qui réalise les dessins qui suivent (z0 est l’affixe du centre du grand cercle, t l’angle de rotation du dessin final, r est le rayon du grand cercle):
cerclexo3r(0,0,20) ok

cerclexo3r(0,0,40) ok

cerclexo3r(0,0,80) ok

cerclexo3r(0,0,80),cerclexo3r(0,pi,80) ok

Faire le programme cerclexo3rc(z0,t,r,c) qui réalise les dessins en couleur qui suivent ((z0 est l’affixe du centre du grand cercle, t l’angle de rotation du dessin final, r est le rayon du grand cercle) et c est un entier désignant la couleur) :
cerclexo3rc(0,0,40,77) ok

axes=0;cerclexo3rc(0,0,80,130),cerclexo3rc(0,pi,80,125) ok

axes=0;cerclexo3rc(0,0,80,108),cerclexo3rc(310-35*i,pi,80,112), cerclexo3rc(310+165*i,0,80,112),cerclexo3rc(620,0,80,116) ok

Chapitre 3  Solution des exercices et des programmes réalisant les télés

3.1  Solution des exercices en syntaxe Xcas

cerclexo1r(z0,t,r,n):={
local L;
L:=NULL;
si n<=0 alors 
  retourne L; 
fsi;
L:=L,cercle(z0,r);
L:=L,cerclexo1r(z0+3*r*exp(i*(t+pi/4))/2,t-pi/4,r/2,n-1);
}:;
cerclexo1rh(z0,t,r,n):={
local L;
L:=NULL;
si n<=1 alors 
  L:=cercle(z0,r),isopolygone(z0,z0-r,-6,affichage=1+rempli);
  retourne L; 
fsi;
L:=L,cercle(z0,r);
L:=L,cerclexo1rh(z0+3*r*exp(i*(t+pi/4))/2,t-pi/4,r/2,n-1);
}:;
cerclexo2r(z0,t,r):={
local L:=NULL;
L:=L,cercle(z0,r);
si r<10 alors retourne L; fsi;
L:=L,cerclexo2r(z0+3*r*exp(i*(t+pi/4))/2,t-pi/4,r/2);
L:=L,cerclexo2r(z0+3*r*exp(i*(t+3*pi/4))/2,t+pi/4,r/2);
}:;
cerclexo3r(z0,t,r):={
local L:=NULL;
L:=L,cercle(z0,r);
si r<10 alors retourne L; fsi;
L:=L,cerclexo3r(z0+3*r*exp(i*(t+pi/6))/2,t-pi/3,r/2);
L:=L,cerclexo3r(z0+3*r*exp(i*(t+pi/2))/2,t,r/2);
L:=L,cerclexo3r(z0+3*r*exp(i*(t+5*pi/6))/2,t+pi/3,r/2);
}:;
cerclexo3rc(z0,t,r,c1):={
local L:=NULL;
L:=L,affichage(cercle(z0,r),rempli+c1);
si r<5 alors retourne L; fsi;
L:=L,cerclexo3rc(z0+3*r*exp(i*(t+pi/6))/2,t-pi/3,r/2,c1+2);
L:=L,cerclexo3rc(z0+3*r*exp(i*(t+pi/2))/2,t,r/2,c1+2);
L:=L,cerclexo3rc(z0+3*r*exp(i*(t+5*pi/6))/2,t+pi/3,r/2,c1+2);
}:;

okonload

3.2  Solution des exercices en syntaxe Python

def cerclexo1r(z0,t,r,n):
    # local L
    L=NULL
    if n<=0 :
        return(L)
    L=L,cercle(z0,r)
    L=L,cerclexo1r(z0+3*r*exp(i*(t+pi/4))/2,t-pi/4,r/2,n-1)

def cerclexo1rh(z0,t,r,n):
    # local L
    L=NULL
    if n<=1 :
        L=cercle(z0,r),isopolygone(z0,z0-r,-6,equal('affichage',1+rempli))
        return(L)
    L=L,cercle(z0,r)
    L=L,cerclexo1rh(z0+3*r*exp(i*(t+pi/4))/2,t-pi/4,r/2,n-1)

def cerclexo2r(z0,t,r):
    # local L=NULL
    L=L,cercle(z0,r)
    if r<10 :
        return(L)
    L=L,cerclexo2r(z0+3*r*exp(i*(t+pi/4))/2,t-pi/4,r/2)
    L=L,cerclexo2r(z0+3*r*exp(i*(t+3*pi/4))/2,t+pi/4,r/2)

def cerclexo3r(z0,t,r):
    # local L=NULL
    L=L,cercle(z0,r)
    if r<10 :
        return(L)
    L=L,cerclexo3r(z0+3*r*exp(i*(t+pi/6))/2,t-pi/3,r/2)
    L=L,cerclexo3r(z0+3*r*exp(i*(t+pi/2))/2,t,r/2)
    L=L,cerclexo3r(z0+3*r*exp(i*(t+5*pi/6))/2,t+pi/3,r/2)

def cerclexo3rc(z0,t,r,c1):
    # local L=NULL
    L=L,affichage(cercle(z0,r),rempli+c1)
    if r<5 :
        return(L)
    L=L,cerclexo3rc(z0+3*r*exp(i*(t+pi/6))/2,t-pi/3,r/2,c1+2)
    L=L,cerclexo3rc(z0+3*r*exp(i*(t+pi/2))/2,t,r/2,c1+2)
    L=L,cerclexo3rc(z0+3*r*exp(i*(t+5*pi/6))/2,t+pi/3,r/2,c1+2)

okonload

3.3  Les programmes des télés en syntaxe Xcas

tete1(z0,r):={
 local L,A;
 L:=NULL;
 L:=L,cercle(z0,r);
 A:=point(z0+r*exp(i*pi/4)/2);
 L:=L,affichage(cercle(A,r/8),4+rempli);
 A:=point(z0+r*exp(3*i*pi/4)/2);
 L:=L,affichage(cercle(A,r/8),4+rempli);
 L:=L,arc(z0+point(r*exp(-3*i*pi/4)/2),z0+point(r*exp(-i*pi/4)/2),-pi/2);
retourne L;
 }:;
tele1(x1,y1,x2,n):={
  local L;
  L:=NULL;
  si n<=0 alors retourne NULL; fsi; 
  L:=L,affichage(rectangle(x1+i*y1,x2+i*y1,.5),0+epaisseur_ligne_2);
  L:=L,tete1((3*x1+x2)/4+i*(y1+(x2-x1)/6),(x2-x1)/6);
  L:=L,tele1((x1+x2)/2-(x2-x1)/50,y1+(x2-x1)/4-(x2-x1)/50,x2-(x2-x1)/50,n-1);
}:; 
tete2(z0,r):={
 local L,A;
 L:=NULL;
 L:=L,cercle(z0,r);
 A:=point(z0+r*exp(i*pi/4)/2);
 L:=L,affichage(cercle(A,r/8),2+rempli);
 A:=point(z0+r*exp(3*i*pi/4)/2);
 L:=L,affichage(cercle(A,r/8),2+rempli);
 L:=L,arc(z0+point(r*exp(-3*i*pi/4)/2),z0+point(r*exp(-i*pi/4)/2),pi/2);
retourne L;
 }:;
tele2(x1,y1,x2,n):={
  local L;
  L:=NULL;
  si n<=0 alors retourne NULL; fsi; 
  L:=L,affichage(rectangle(x1+i*y1,x2+i*y1,.5),1+epaisseur_ligne_2);
  L:=L,tete2((3*x1+x2)/4+i*(y1+(x2-x1)/6),(x2-x1)/6);
  L:=L,tele2((x1+x2)/2-(x2-x1)/50,y1+(x2-x1)/4-(x2-x1)/50,x2-(x2-x1)/50,n-1);
}:; 
tele12(x1,y1,x2,n):={
  local L;
  L:=NULL;
  si n<=0 alors retourne NULL; fsi; 
  L:=L,affichage(rectangle(x1+i*y1,x2+i*y1,.5),0+epaisseur_ligne_2);
  L:=L,tete1((3*x1+x2)/4+i*(y1+(x2-x1)/6),(x2-x1)/6);
  L:=L,tele21((x1+x2)/2-(x2-x1)/50,y1+(x2-x1)/4-(x2-x1)/50,x2-(x2-x1)/50,n-1);
}:; 
tele21(x1,y1,x2,n):={
  local L;
  L:=NULL;
  si n<=0 alors retourne NULL; fsi; 
  L:=L,affichage(rectangle(x1+i*y1,x2+i*y1,.5),1+epaisseur_ligne_2);
  L:=L,tete2((3*x1+x2)/4+i*(y1+(x2-x1)/6),(x2-x1)/6);
  L:=L,tele12((x1+x2)/2-(x2-x1)/50,y1+(x2-x1)/4-(x2-x1)/50,x2-(x2-x1)/50,n-1);
}:; 

okonload

3.4  Les programmes des télés en syntaxe Python

def tete1(z0,r):
    # local L,A
    L=NULL
    L=L,cercle(z0,r)
    A=point(z0+r*exp(i*pi/4)/2)
    L=L,affichage(cercle(A,r/8),4+rempli)
    A=point(z0+r*exp(3*i*pi/4)/2)
    L=L,affichage(cercle(A,r/8),4+rempli)
    L=L,arc(z0+point(r*exp(-3*i*pi/4)/2),z0+point(r*exp((-(i))*pi/4)/2),-pi/2)
    return(L)

def tele1(x1,y1,x2,n):
    # local L
    L=NULL
    if n<=0 :
        return(NULL)
    L=L,tete1((3*x1+x2)/4+i*(y1+(x2-x1)/6),(x2-x1)/6)
    L=L,affichage(rectangle(x1+i*y1,x2+i*y1,0.5),0+epaisseur_ligne_2)
    L=L,tele1((x1+x2)/2-(x2-x1)/50,y1+(x2-x1)/4-(x2-x1)/50,x2-(x2-x1)/50,n-1)

def tete2(z0,r):
    # local L,A
    L=NULL
    L=L,cercle(z0,r)
    A=point(z0+r*exp(i*pi/4)/2)
    L=L,affichage(cercle(A,r/8),2+rempli)
    A=point(z0+r*exp(3*i*pi/4)/2)
    L=L,affichage(cercle(A,r/8),2+rempli)
    L=L,arc(z0+point(r*exp(-3*i*pi/4)/2),z0+point(r*exp((-(i))*pi/4)/2),pi/2)
    return(L)

def tele2(x1,y1,x2,n):
    # local L
    L=NULL
    if n<=0 :
        return(NULL) 
    L=L,tete2((3*x1+x2)/4+i*(y1+(x2-x1)/6),(x2-x1)/6)
    L=L,affichage(rectangle(x1+i*y1,x2+i*y1,0.5),1+epaisseur_ligne_2)
    L=L,tele2((x1+x2)/2-(x2-x1)/50,y1+(x2-x1)/4-(x2-x1)/50,x2-(x2-x1)/50,n-1)

def tele12(x1,y1,x2,n):
    # local L
    L=NULL
    if n<=0 :
        return(NULL) 
    L=L,tete1((3*x1+x2)/4+i*(y1+(x2-x1)/6),(x2-x1)/6)
    L=L,affichage(rectangle(x1+i*y1,x2+i*y1,0.5),0+epaisseur_ligne_2)
    L=L,tele21((x1+x2)/2-(x2-x1)/50,y1+(x2-x1)/4-(x2-x1)/50,x2-(x2-x1)/50,n-1)

def tele21(x1,y1,x2,n):
    # local L
    L=NULL
    if n<=0 :
        return(NULL) 
    L=L,tete2((3*x1+x2)/4+i*(y1+(x2-x1)/6),(x2-x1)/6)
    L=L,affichage(rectangle(x1+i*y1,x2+i*y1,0.5),1+epaisseur_ligne_2)
    L=L,tele12((x1+x2)/2-(x2-x1)/50,y1+(x2-x1)/4-(x2-x1)/50,x2-(x2-x1)/50,n-1)

okonload

Clone Efface + - ->   Restart Exec. tout