La programmation récursive
Cette façon toute particulière de penser la démarche algorithmique permet de résoudre des problèmes à priori complexes, mais qui le sont moins pour un ordinateur, du moment qu'il possède une mémoire plus importante que la notre !
Un jeu bien connu : Les tours de Hanoï
Il s'agit d'un jeu inventé par le mathématicien Édouard Lucas en 1883. Il est constitué de trois piquets verticaux, notés 1, 2 et 3 et de n disques superposés, de tailles strictement décroissantes, avec un trou au centre et enfilés autour du piquet 1.
Le but du jeu consiste à déplacer l'ensemble des disques pour que ceux-ci se retrouvent enfilés autour du piquet repéré 3 en respectant les règles suivantes :
- les disques sont déplacés un par un
- un disque ne doit pas se retrouver au-dessus d'un disque plus petit.
(On suppose évidemment que cette dernière règle est également respectée dans la configuration de départ).
>> Avec 3 disques...vous devriez y arriver sans soucis ... mais avec 5, ou plus ? Essayez donc !
L'ordinateur n'y verra aucune difficulté supplémentaire hormis la mémoire !
Pour 3 disques :
**********************************************
deplacer un disque de 1 vers 3 -> 1 coups
deplacer un disque de 1 vers 2 -> 2 coups
deplacer un disque de 3 vers 2 -> 3 coups
deplacer un disque de 1 vers 3 -> 4 coups
deplacer un disque de 2 vers 1 -> 5 coups
deplacer un disque de 2 vers 3 -> 6 coups
deplacer un disque de 1 vers 3 -> 7 coups
Soit un total de 7 coups
Pour 5 disques :
**********************************************
Deplacer un disque de 1 vers 3 -> 1 coups
Deplacer un disque de 1 vers 2 -> 2 coups
Deplacer un disque de 3 vers 2 -> 3 coups
Deplacer un disque de 1 vers 3 -> 4 coups
Deplacer un disque de 2 vers 1 -> 5 coups
Deplacer un disque de 2 vers 3 -> 6 coups
Deplacer un disque de 1 vers 3 -> 7 coups
Deplacer un disque de 1 vers 2 -> 8 coups
Deplacer un disque de 3 vers 2 -> 9 coups
Deplacer un disque de 3 vers 1 -> 10 coups
Deplacer un disque de 2 vers 1 -> 11 coups
Deplacer un disque de 3 vers 2 -> 12 coups
Deplacer un disque de 1 vers 3 -> 13 coups
Deplacer un disque de 1 vers 2 -> 14 coups
Deplacer un disque de 3 vers 2 -> 15 coups
Deplacer un disque de 1 vers 3 -> 16 coups
Deplacer un disque de 2 vers 1 -> 17 coups
Deplacer un disque de 2 vers 3 -> 18 coups
Deplacer un disque de 1 vers 3 -> 19 coups
Deplacer un disque de 2 vers 1 -> 20 coups
Deplacer un disque de 3 vers 2 -> 21 coups
Deplacer un disque de 3 vers 1 -> 22 coups
Deplacer un disque de 2 vers 1 -> 23 coups
Deplacer un disque de 2 vers 3 -> 24 coups
Deplacer un disque de 1 vers 3 -> 25 coups
Deplacer un disque de 1 vers 2 -> 26 coups
Deplacer un disque de 3 vers 2 -> 27 coups
Deplacer un disque de 1 vers 3 -> 28 coups
Deplacer un disque de 2 vers 1 -> 29 coups
Deplacer un disque de 2 vers 3 -> 30 coups
Deplacer un disque de 1 vers 3 -> 31 coups
Soit un total de 31 coups
>> On remarquera que le nombre de coups N vaut : N=2n-1 où n est le nombre de disques
Autre exemple de récursivité : Les fractales, de bien jolies figures...
Une figure fractale est une courbe ou une surface très irrégulière, avec une auto-similarité plus ou moins marquée.
→ Certaines structures de la figure se retrouvent un peu partout et à toutes les échelles.
Ddifférents agrandissements qui mettent en évidence l'auto-similarité :
La nature recèle d'éléments emprunts d'auto-similarité : flocons de neige, fougères, le chou romanesco...
En mathématiques, en informatique, en biologie, ..., nous faisons souvent face à des situations où un problème doit être résolu en utilisant une méthode de résolution qui est répétée plusieurs fois.
Le flocon de Kock :
Le flocon de von Koch est l'une des premières courbes fractales à avoir été décrite (bien avant l'invention du terme « fractal(e) »). Elle a été inventée en 1906 par le mathématicien suédois Helge von Koch.
Quelques lignes de codes suffisent à construire cette figure fractale :
from turtle import *
def kock(longueur, generation):
if generation==0:
forward(longueur)
else:
kock(longueur/3,generation-1)
left(60)
kock(longueur/3,generation-1)
right(120)
kock(longueur/3,generation-1)
left(60)
kock(longueur/3,generation-1)
right(360)
reset()
n=3
longueur=500
for i in range(1,4):
kock(longueur,n)
right(120)
exitonclick()