2.9 LA RÉCURSIVITÉ


INTRODUCTION

Vous connaissez peut-être la comptine de l'histoire de l'homme à la dent creuse :


Il y avait une fois un homme, 
Qui avait une dent creuse, 
Cette dent creuse contenait une boîte 
Et cette boîte contenait une lettre 
Et cette lettre racontait qu'
Il y avait une fois un homme,
Qui avait une dent creuse ...


Si vous définissez un objet en utilsant dans la définition le nom de l'objet, votre définition est dite récursive.
Un exemple type : une définition récursive est une définition récursive.
Vous connaissez sûrement les Poupées russes : Une matryoshka contient un  matriochka légèrement plus petite, qui contient elle-même une matriochka, qui contient elle-même une ...

L'ESCALIER RÉCURSIF


Nous voulons construire un escalier de 3 marches.

Définition récursive : un escalier de 3 marches se compose d'une marche puis d'un escalier de 2 marches, lui-même composé d'une marche et d'un escalier d'1 marche, lui-même composé d'1 marche et d'un escalier de 0 marche.

Construire un escalier de n marches revient donc à construire une marche, puis construire un escalier de (n-1) marches.

En programmation, si on va donc définir ainsi la fonction construire_escalier(nb_marches)

  def construire_escalier(n):
     	constuire_une_marche()
     	construire_escalier(n-1)

La fonction construire_escalier(n) construit une marche puis appelle la fonction constuire_escalier(n-1), etc ...

Pour arrêter le processus il suffit de teste la valeur de la variable n, avant de construire une marche supplémentaire.

  if n == 0:
    return

Votre programme se présente donc ainsi :



A MEMORISER

La récursivité est une méthode fondamentale de résolution en mathématiques et en informatique, dans laquelle un problème est résolu en le simplifiant peu à peu.

À première vue, il semble étrange que l'on puisse résoudre un problème en supposant que l'on connaît déjà la solution.
Mais nous résolvons un proglème plus proche de la solution, donc plus facile.
Nous utilisons pour cela un paramètre n dans une fonction f(n).

  def f(n):
    ...
Dans la ré-utilisation de f le paramètre est décrémenté et devient n-1 :
  def f (n):
    ...
    f (n-1)
    ...
Une telle fonction pourrait ne jamais s'arrêter, et pour éviter cela, vous mettez une condition sur la valeur de la variable, avant de ré-appeler la fonction.
  def f (n):
    si n == 0:
       retour
    ...
    f (n - 1)
    ...
Le mot-clé return arrête l'exécution de la fonction.

L'ARBRE DE PYTHAGORE


La récursivité permet de créer de magnifiques graphiques.
L'arbre de Pythagore est construit  à partir de carrés séparés de triangles rectangles. Il se construit de la manière suivante :

Pour construire un triangle de pythagore, il faut procéder ainsi :

1
Dessinez un carré ABCD avec la base côté AD

2
Dessinez un triangle rectangle isocèle BD1C sur le côté BC

3
Dessinez deux carrés A1B1C1D1 et A2B2C2D2 ayant respectivement comme base A1D1  et A2D2

La programmation récursive n'est pas facile au début, c'est pourquoi nous vous proposons ci-dessous un guide détaillant le mode opératoire :

Définir un carré (s) de commande avec laquelle la tortue un carré de dossiers et la rentabilité de longueur à la position initiale avec la ligne supérieure de la vue 

Définir l'arbre (s) de commande qui est un arbre basé sur un carré de longueur côté de distingué. Dans la définition que vous arbre () ne peut pas utiliser à nouveau. Important: Après avoir dessiné l'arbre, la tortue est de retour dans la position de départ de la première ligne de vue. Vous pensez progressivement, comme si vous étiez la tortue (le nouvellement ajouté est affichée en gris). 



A MEMORISER

Dans de nombreuses figures définies de manière récursive, il est important que la tortue retourne à son emplacement initial et retrouve son orientation initiale.

EXERCICES


1

Saisissez dans l'éditeur les deux programmes ci-dessous et enregistrez-les.

Quelle est la différence essentielle entre les deux programmes ci-dessous ?

Examinez notamment l'emplacement et la direction de la tortue après la fin du programme.

2

L'arbre binaire ci-contre est une figure récursive bien connue.

Créez la fonction branche(taille) qui construit une seule branche de la taille indiquée puis revient à son point de départ.

A la ligne du programme de la fonction branche(taille) correspondant au sommet de la branche, divisez la taille par 2, tournez de 45° à gauche et appelez la fonction branche(nouvelle taille)

Tournez ensuite de 90° à droite et appelez la fonction branche(nouvelle taille)

Ajoutez ensuite en tout début de fonction la condition de test de la valeur de la taille : si la taille est inférieure à une certaine valeur, la fonction doit s'arrêter (par la commande return() )

Le programme principal n'a plus qu'à appeler la fonction branche (200)


3

Dessiner la figure d'étoile ci-contre.

Commencez par créer la fonction etoile(taille) qui dessine une simple étoile à 6 branches (repeat) et revenez au centre.

A la ligne du programme de la fonction etoile(taille)  correspondant au sommet de la branche, divisez la taille par 3, et appelez la fonction étoile(nouvelletaille)

Ajoutez ensuite en tout début de fonction la condition de test de la valeur de la taille : si la taille est inférieure à une certaine valeur, la fonction doit s'arrêter (par la commande return() )
Le programme principal n'a plus qu'à appeler la fonction etoile (200).

La commande hideTurtle() permettra à la toirtue de dessiner beaucoup plus rapidement la figure.


4 *.


Vous devez dessiner un arbre, qui ressemble presque à un vrai arbre.

Définissez pour cela la fonction récursive branche(taille), construite comme ceci :

La récursivité doit cesser lorsqu'une taille (variable s) de la tige est inférieure à 2 (taille limite)

Mémorisez les coordonnées de départ dans les variables x0 et y0 à l'aide des commandes getX() et getY()

Vous avancez d'une distance égale à s/3.

Tournez à gauche de 30 °

Appellez la fonction branche avec une taille de branche s1 égale à 2*s/3

Vous tournez d'un angle de 30 ° vers la droite (pour réorienter la tortue)

Vous avancez d'une distance égale à s/6

Appellez la fonction branche avec une taille de branche s2 égale à s/2

Vous tournez à droite de 25°,

Avancez de s/3

Appellez la fonction branche avec une taille de branche s2 égale à s/2

Vous tournez d'un angle de 25 ° vers la gauche (pour réorienter la tortue)

Retournez aux coordonnées d'origine de la branche à l'aide de la l'instruction     setPos(x0,y0)

Vous appelez ensuite la fonction branche avec une taille de 200 et une limite à 2


 Changez la limite à 100

Changez la limite à 50 

Changez la limite à 20 

Changez la limite à 10  

Changez la limite à 1   

Traduit assez librement (et légèrement adapté) de PROGRAMMIERKONCEPT de J. Arnold, T. Kohn, et Aegidius Plüss