import turtle as t
"""Turtle : mouvements elementaires"""

# init : taille ecran en pixels, clear ecran, reset des variables
t.screensize(500,500)
t.reset()
t.hideturtle() # pour aller plus vite
t.degrees() # angles en deg

''' essai turtle qui ne ressemble a rien'''

def carre(c, colorstring):
    """dessine un carre de cote c et le remplit de color"""
    t.fillcolor(colorstring)
    t.begin_fill()
    for i in range(4):
        t.forward(c)
        t.right(90)
    t.end_fill()
    
# parametres deplacement
un = 30
deux = 2*un

# un carre
t.goto(10,10)
t.down()
carre(deux, "black")

# on se deplace sans laisser de trace
t.up()
t.goto(un, un)
t.down()

# un carre plus petit
carre(un, "white")

# et un autre carre en couleur lie au precedent
t.goto(5*un,5*un)
t. pencolor("red")
t.pensize(2) 
t.hideturtle() # pour aller plus vite
carre(un, "blue")

# pour que le trace reste a l ecran
#t. mainloop()

# pour attendre avant d'effacer la fenetre turtle
v = input("OK ?")
t.reset()

def segment(d, n, color="black"):
    """segment de von Koch
    recursion sur n pour decouper le segment de longueur d et
    tracer d (longueur du segment) pixels si n==0"""
    t.pencolor(color)        

    if n==0:
        t.forward(d)
    else:
    
        dsur3 = d//3
        segment(dsur3, n-1)
        t.left(60)
        segment(dsur3, n-1)
        t.right(120)
        segment(dsur3, n-1)
        t.left(60)
        segment(dsur3, n-1)

# taille
d = 300
#nbiter = input("nombre d'iterations = ")
nbiter = 1
h = 150 # espace vertical entre 2 traces

# point de depart
a = (-200, 400)

# trace et changement point de depart
for i in range(nbiter):
    # deplacement au point de depart
    t.up()
    t.goto(a)
    t.down()

    # trace 
    segment(d, i)
    
    # maj point de depart
    a = (a[0], a[1] - h)

# pour attendre avant d'effacer la fenetre turtle
v = input("OK ?")
t.reset()

# pour que le trace reste a l ecran
#t. mainloop()

'''trace (nbiter) flocons de VK'''


def flocon(d, n, color="black"):
    ''' trace flocon de VK en utilisant segment'''
    segment(d, n, color)
    t.right(120)
    segment(d, n, color)
    t.right(120)
    segment(d, n, color)
    t.right(120)

#nbiter = input("nombre d'iterations = ")
nbiter = 3
h = 150 # espace vertical entre 2 traces
a = (-200, 200) # point de depart
d = 84  # taille

# trace et changement point de depart
for i in range(nbiter):
    # deplacement au point de depart
    t.up()
    t.goto(a)
    t.down()

    # trace 
    flocon(d, i)
    
    # maj point de depart
    a = (a[0], a[1] - h)

# pour attendre avant d'effacer la fenetre turtle
v = input("OK ?")
t.reset()

Autre figure géométrique récursive

triangle de Sierpinsky

sierpinsky

/>

Structures de données récursives¶

liste chainée
/>
arbre, arbre binaire
/>

application : arbre du code Morse (point, tiret) />

application : représentation d'une expression />

Intérêts de la récursion¶

Avantage¶

Une solution algorithmique récursive est souvent plus simple, plus lisible, plus facile à prouver qu'une solution itérative

exemple caractéristique : les tours de Hanoi (voir exercice de td)

Animation de résolution :

Tower of Hanoi 4 par André Karwath (wikimediacommons)

Inconvénient¶

L'éxecution de la solution récursive est plus compliquée

gestion d'une pile d'appels de fonctions : la pile d'exécution

L'exécution de la solution récursive peut provoquer des débordements de la mémoire

Paradigme diviser pour régner¶

On divise le problème en des problèmes similaires de taille moindre,

et ce récursivement jusqu'à obtenir un problème suffisament simple (petit) pour le résoudre

Approche qui conduit à une solution naturellement ... récursive !

exemples caractéristiques car plus efficaces qu'une solution itérative
- recherche dichotomique dans un ensemble trié
- exponentiation rapide : $$x^{2p} = (x^p)^2$$ et $$x^{2p+1} = x \cdot (x^p)^2$$

Fonctions numériques récursives¶

Une définition, deux écritures équivalentes

forme itérative $$n ! = 1 \times 2 \times \cdot \times (n-1) \times n$$
forme récursive $$n ! = n \times (n-1) ! \text{ avec } 1! = 1$$

Remarque : ces définitions ont un sens pour $n>0$. La valeur de $0!$ doit être définie de façon supplémentaire.

Factorielle : forme itérative¶

def f(n):
    """Calcul de factorielle n -- version itérative
    entrée : n 
    sortie n!
    """
    res = 1
    for i in range(2,n+1):
        res = res * i
    return res

print("3! =", f(3))
print("1! =", f(1))

3! = 6
1! = 1

# bien que non défini a priori
print("0! =", f(0))
# et même n'importe quoi !
print("-3! =", f(-3))

0! = 1
-3! = 1

ATTENTION : il faudrait **vérifier la validité du paramètre effectif**

Exercice¶

pourquoi ?
comment ?

Factorielle : forme récursive¶

On applique la définition récursive : $n ! = n \times (n-1) !$

Oui, oui ! On a oublié de définir $0 !$.

On l'écrit quand même ...

Premier essai¶

def f(n):
    """Calcul de factorielle n -- version récursive
    entrée : n 
    sortie n!
    """
    return n*f(n-1) # récursion

print("1! =", f(1))

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
 in ()
      6     return n*f(n-1) # récursion
      7 
----> 8print("1! =", f(1))

 in f(n)
      4     sortie n!
      5     """
----> 6return n*f(n-1) # récursion
      7 
      8 print("1! =", f(1))

... last 1 frames repeated, from the frame below ...

 in f(n)
      4     sortie n!
      5     """
----> 6return n*f(n-1) # récursion
      7 
      8 print("1! =", f(1))

RecursionError: maximum recursion depth exceeded

INFO: python limite à 100 le nombre d'appels récursifs

Heureusement ... ce qui nous sauve ici !

Terminaison : pour arrêter les appels récursifs !!!!¶

def f(n):
    """Calcul de factorielle n -- version récursive
    entrée : n 
    sortie n!
    """
    if n == 1:          # terminaison
        return 1
    else:
        return n*f(n-1) # récursion

print("3! =", f(3))
print("1! =", f(1))

3! = 6
1! = 1

ATTENTION : pourquoi ne pas demander de calculer `f(0)`?

2 instructions return :

la première retourne une valeur terminale
la seconde provoque un appel récursif (à elle-même) avant d'effectuer un quelconque calcul !
. en effet le second opérande de la multiplication n'est pas encore connu ...

Autre écriture avec 1 seul return :

def f(n):
    """Calcul de factorielle n -- version récursive avec un seul return
    entrée : n 
    sortie n!
    """
    if n == 1:          # terminaison
        res = 1
    else:
        res = n * f(n-1) # récursion
    return res

print("3! =", f(3))
print("1! =", f(1))

3! = 6
1! = 1

Bien comprendre les appels récursifs !¶

Deux solutions :

Facile : utilisons http://pythontutor.com/live.html#mode=edit pour calculer $5 !$
Plus lourd : on va, de façon exceptionnelle, mettre des affichages dans le corps de la fonctions récursive pour bien comprendre. Pour cela, on décortique bien la fonction.

def f(n):
    """Calcul de factorielle n -- version récursive
    entrée : n 
    sortie n!
    """
    # pour voir les imbrications des appels
    global l
    # on met a jour indent avant chaque return
    
    l = l + 1 # on ajoute .... à chaque appel
    indent = l * "...."
    print(indent, "entrée dans f(", n, ")")
    
    if n == 1:     
        print(indent, "terminaison : on renvoit 1 pour n = ", n)
        l = l - 1 # on enleve .. avant un return
        return 1
    
    else:
        print(indent, n,"* f(", n-1,") = ?")
    
        print(indent, "appel de f(", n-1,")")
        r = f(n-1)
        print(indent, "on a calculé f(", n-1, ")")

        p = n * r
        print(indent, "on a fait le produit ", n,"* f(", n-1,")")
        print(indent, "Retour de la valeur", p)

        l = l - 1 # on enleve .. avant un return
        return p # récursion

l = -1
f(4)

 entrée dans f( 4 )
 4 * f( 3 ) = ?
 appel de f( 3 )
.... entrée dans f( 3 )
.... 3 * f( 2 ) = ?
.... appel de f( 2 )
........ entrée dans f( 2 )
........ 2 * f( 1 ) = ?
........ appel de f( 1 )
............ entrée dans f( 1 )
............ terminaison : on renvoit 1 pour n =  1
........ on a calculé f( 1 )
........ on a fait le produit  2 * f( 1 )
........ Retour de la valeur 2
.... on a calculé f( 2 )
.... on a fait le produit  3 * f( 2 )
.... Retour de la valeur 6
 on a calculé f( 3 )
 on a fait le produit  4 * f( 3 )
 Retour de la valeur 24

24

CONSEIL : bien regarder le moment où on effectue la **première** multiplication

Exercice :

Combien de variables locales r et p ont été utilisées ?

Réponse :

Chaque appel à f() introduit une nouvelle paire s et p
Ces variables sont introduites et évaluées dans l'environnement (le contexte) de l'appel concerné

Ces notions seront approndies plus loin.

Exponentiation entière rapide¶

Objectif : calculer $x^n$ où $x$ est un réel et $n$ un entier positif.

Une première récursion¶

Elle est basée sur la relation récursive : $x^n = x \times x^{n-1}$ et $x^0 = 1$, pour $n \ge 0$.

def expo(x, n):
    '''calcule x**n : version récursive naturelle 
    entrées : x (float), n (int)'''
    if n == 0:
        return 1
    else:
        return x * expo(x, n-1)
    
expo(2,10)

1024

Exercice :

Ecrire une autre version avec 1 seul return
Ecrire une version itérative

Une seconde récursion beaucoup plus ... rapide¶

Autre écriture de $x^n$ avec des airs de dichotomie :)

$x^{2p} = (x^p)^2$ -- c'est simple et récursif, non ?
$x^{2p+1} = x \times (x^p)^2$ -- c'est simple et aussi récursif, non ?

def expo_rapide(x,n):
    '''calcule x**n : version récursive rapide 
    entrées : x (float), n (int)'''
    if n == 0:
        return 1
    else:
        r = expo_rapide(x, n//2)
        if (n % 2 == 0): # n est pair
            res = r * r
        else:            # n est impair
            res = x * r * r
        return res
    
expo_rapide(2,100)

1267650600228229401496703205376

Exercice

Exhibons que expo_rapide()est effectivement plus rapide que expo

python permet de mesurer facilement le temps d'exécution d'un script
ipython le permet avec des "magic functions" : elles commencent avec un %

# %time mesure le temps d'exécution d'une script
%time expo(2,200)
%time expo_rapide(2,200)

CPU times: user 94 µs, sys: 11 µs, total: 105 µs
Wall time: 110 µs
CPU times: user 10 µs, sys: 1e+03 ns, total: 11 µs
Wall time: 14.1 µs

1606938044258990275541962092341162602522202993782792835301376

Mesurer de façon fiable des temps d'exécution est plus difficile qu'il parait : l'ordinateur est rusé ...

on répéter dans une boucle la partie qu'on veut mesurer (si elle prend très peu de temps) --> option -n
on peut répéter les mesures et les analyser : garder la meilleure, regarder la moyenne ... --> option r

# timeit plus fiable : répète plusieurs mesures
%timeit expo(3,20)
%timeit expo_rapide(3,20)

%timeit -n 100 expo(3,20)
%timeit -n 100 expo_rapide(3,20)

%timeit -r 5 expo(3,20)
%timeit -r 5 expo_rapide(3,20)

100000 loops, best of 3: 3.42 µs per loop
1000000 loops, best of 3: 1.28 µs per loop
100 loops, best of 3: 3.2 µs per loop
100 loops, best of 3: 1.21 µs per loop
100000 loops, best of 5: 3.36 µs per loop
1000000 loops, best of 5: 1.26 µs per loop

Fibonacci ou l'inefficacité de la récursion¶

La suite de Fibonnaci est définie par une récurrence d'ordre 2 :

$$F(n+1) = F(n) + F(n-1);$$

ce qui nécessite de connaître 2 valeurs de départ : $$F(0) = F(1) = 1.$$

Solution récursive¶

L'expression est naturellement récursive donc ...

def fibo(n):
    '''Fibonacci : solution récursive classique '''
    if n == 0 or n == 1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)
    
for i in range(10):
    print(i,":", fibo(i))

0 : 1
1 : 1
2 : 2
3 : 3
4 : 5
5 : 8
6 : 13
7 : 21
8 : 34
9 : 55

La suite va nous permettre de mieux voir l'inefficacité de cette solution récursive !

Appels récursifs : environnement, pile d'éxecution, pile et arbre des appels¶

On présente maintenant des notions liées à la mise en oeuvre des appels de fonction dans le cadre récursif.
On en restera surtout aux principes, aux abstractions algorithmiques.
Les aspects plus détaillés de la mise en oeuvre (implantation du mécanisme d'appel de fonction) sont étudiés en deuxième année.

Environnement¶

Chaque appel récursif nécessite de construire dynamiquement un nouvel environnement :

où retourner le résultat de l'appel : une adresse de retour (ou des adresses)
les paramètres effectifs de l'appel
les variables locales nécessaire au traitement demandé

En pratique, on ne connait pas le nombre de fois où une/des fonctions sont appelées. Toutes ces informations sont donc stockées dans une pile d'exécution ou pile des appels. Une pile est une structure de donnée adaptée au stockage et à une certain type de traitements : empiler et dépiler.

Pile d'exécution¶

La pile d'exécution est la mémoire associée nécessaire au stockage des paramètres d'appel, des adresses de retour, des variables locales

gérée par le langage de programmation : une pile LIFO de taille préfixée
mais risque de débordement mémoire si appels imbriqués (sans libération de la place occupée) trop nombreux

En python : 1000 appels au maximum ou trop volumineux

Imaginons un paramètre tableau de grande taille réduit récursivement de 1 élément par 1 élément ...
exemple : sommer récursivement les n valeurs d'un tableau
qui plus est si la récursion est multiple comme la suite de Fibonacci : $f(n+1) = f(n) + f(n-1)$

En pratique : `stack overflow !` est le message classique quand ... ça ne va pas :

Pile des appels¶

La pile des appels est une abstraction algorithmique qui représente la logique de la pile d'exécution en se limitant à l'identifiant de chaque appel. On ne détaille pas l'environnement de chaque appel.

Arbre des appels récursifs¶

L'arbre des appels récursifs est une autre abstraction algorithmique de l'ensemble des appels d'un traitement récursif.
Le parcours des noeuds d'un arbre se représente aussi avec une pile ... d'où la connection entre ces deux abstractions du traitement de la récursion.

Illustration sur la factorielle récursive¶

Calcul de fact(4)

factorielle(4)

/>

''' arbre des appels du calcul de fact(4)'''

import graphviz as gvz
import functools
fact4 = gvz.Digraph(format='jpg')
fact4.node('f4', label='fact(4)')
fact4.node('f3', label='fact(3)')
fact4.node('f2', label='fact(2)')
fact4.node('f1', label='fact(1)', color='red')
fact4.edge('f4', 'f3')
fact4.edge('f3', 'f2')
fact4.edge('f2', 'f1')

file_out = fact4.render('fig/fact4_dot')

arbre des appels¶

La représentation suivante exhibe l'arbre des appels récursif de f

from IPython.display import display, Image
print(__doc__)
display(Image('fig/fact4_dot.jpg'), width=30)

 arbre des appels du calcul de fact(4)

import graphviz as gvz
import functools

digraph = functools.partial(gvz.Digraph, format='jpg')

def add_nodes(graph, nodes):
    for n in nodes:
        if isinstance(n, tuple):
            graph.node(n[0], **n[1])
        else:
            graph.node(n)
    return graph

def add_edges(graph, edges):
    for e in edges:
        if isinstance(e[0], tuple):
            graph.edge(*e[0], **e[1])
        else:
            graph.edge(*e)
    return graph

''' arbre complet de l'évaluation fact(4)'''
fact4_complet = add_edges(
    add_nodes(digraph(), [
        ('4'), ('3'), ('2'),
        ('f4', {'label': 'fact(4)'}),
        ('f3', {'label': 'fact(3)'}),
        ('f2', {'label': 'fact(2)'}),
        ('f1', {'label': 'fact(1)', 'color':'red'}),
    ]),
    [
        ('f4', '4'),
        ('f3', '3'),
        ('f2', '2'),
        ('f4', 'f3'),
        ('f3', 'f2'),
        ('f2', 'f1')
    ]
).render('fig/fact4_complet')

from IPython.display import display, Image
print(__doc__)
display(Image('fig/fact4_complet.jpg'), width=30)

 arbre complet de l'évaluation fact(4)

pile des appels¶

L'évolution de la pile des appels lors deu calcule de $4!$ s'obtient en parcourant l'arbre des appels.
On note fact( ) par f( ).

               f(1)
          f(2) f(2) f(2)
     f(3) f(3) f(3) f(3) f(3)
f(4) f(4) f(4) f(4) f(4) f(4) f(4) .

environnements succcessifs pour factorielle(3)¶

On peut le détailler un peu plus dans ce cas simple.

appel = f(3)

def f(n):
    """Calcul de factorielle n -- version récursive
    entrée : n 
    sortie n!
    """
    if n == 1:     
        return 1   
    else:
        r = f(n-1)
        p = n * r
        return p # récursion

L'environnement de chaque appel est décrit par une colonne du tableau suivant.

.	0	1	2	3
1	r=f(3)	n=3
2		r=f(2)	n=2
3			r=f(1)	n=1
4				return 1
5			p=2*1
6			return 2
7		p=3*2
8		return 6
9	r = 6

Illustration sur le calcul récursif de Fibonacci.¶

arbre des appels¶

Le calcul de fibo(4) correspond à un parcours "en profondeur d'abord" de l'arbre des appels suivant.

arbre />appels fibo(4)

pile des appels récursifs¶

On note fibo() par f()
Les appels récursifs sont empilés (avec leur environnement) dans une pile d'appels
Les appels avec terminaison permettent de dépiler l'appelant
L'appel principal est exécuté une fois la pile vidée

               f(1) f(0)
          f(2) f(2) f(2) f(2)      f(1)                f(1) f(0)
     f(3) f(3) f(3) f(3) f(3) f(3) f(3) f(3)      f(2) f(2) f(2) f(2)
f(4) f(4) f(4) f(4) f(4) f(4) f(4) f(4) f(4) f(4) f(4) f(4) f(4) f(4) f(4)

Retour sur l'inefficacité du calcul récursif de Fibonacci¶

Exercice : comptons le nombre d'appels à fibo() dans l'évaluation de fibo(4).

fibo(4)	#appels
fibo(0)	2
fibo(1)	3
fibo(2)	2
fibo(3)	1
total	8

Ces évaluations intermédiaires répétées engendrent des sur-coûts en mémoire et en calcul qui dégradent l'efficacité de l'évaluation récursive de fibo( ).

environnements et pile d'exécution¶

Profitons du python tutor pour visualiser l'enchaînement des appels et l'évolution de l'environnement :

https://goo.gl/mHi50H

Solution itérative¶

Analyse :

pour calculer $F(n)$, il faut avoir calculé les 2 précédents : $F(n-1)$ et $F(n-2)$
et ainsi de suite ...
donc on part de $F(0)$ et $F(1)$
et on avance dans l'itération en stockant
- les 2 dernières valeurs calculées
- toutes les valeurs déjà calculées

La solution itérative est plus efficace car elle évite de re-calculer les termes déjà calculés.

Exercice¶

Reprendre ça sous http://pythontutor.com/live.html#mode=edit

Recherche dichotomique¶

Principes¶

Objectif
Rechercher si une valeur apparait dans un tableau de valeurs triées
Répondre vrai si la valeur est dans le tableau, faux sinon

Hypothèse de départ
Les valeurs sont rangées de façon triée (on ne le dira jamais assez !)
par ordre croissant par exemple

Principe
Un algorithme diviser pour régner où chaque division réduit la recherche à un ensemble de taille moitié, l'autre ensemble n'étant plus considéré

diviser :
- on partage en 2 par la moitié le tableau trié
régner :
- on compare la valeur cherchée à la valeur médiane du tableau
- si besoin, on en déduit la moitié gauche ou droite du tableau qui contient la valeur cherchée
- on recommence la recherche sur la "bonne moitié"

Algorithme itératif¶

Analyse

Il faut :

itérer :
- le test de la valeur de l'indice milieu
- le découpage en 2 du tableau
arrêter :
- quand on a trouvé la valeur cherchée
- ou si la taille du tableau est égale à zéro (tableau vide)
retourner un booléen

Codage

L'appel s'effectue en indiquant :
- la valeur cherchée
- le tableau
- sa taille
Le nombre d'itérations n'est a priori pas connu (il est borné en revanche) donc boucle while
L'indice milieu est obtenu avec une division entière // sachant que le milieu entre $a$ et $b$ est $(a+b)/2$
D'une itération à l'autre :
- choisir la partie gauche ou droite du tableau revient à changer l'indice de début et de fin du prochain tableau à traiter : on introduit des indices g, d et m pour désigner les indices de gauche, de droite et du milieu
- la taille est divisée par 2

def dichotomie_iterative(val, t, dim_t):
    '''recherche dichotomique : version itérative
    entrées - val :int cherché
            - t : tableau d'int de taille dim_t, trié par ordre croissant
    sortie : vrai si val est dans t, faux sinon

    '''
    present = False # la réponse
    g = 0          # indice de gauche du tableau exploré
    d = dim_t - 1  # indice de droite du tableau exploré
    
    while (present == False) and (g <= d):
        m = (g + d)//2   # indice milieu de t[g,d]
        if t[m] == val:
            present = True
        elif t[m] > val: # val est dans la partie gauche : t[g,m-1]
            d = m - 1
        else:            # val est dans la partie droite : t[m+1,d]
            g = m + 1
    return present

'''appel de recherche dichotomique (itérative)'''

tab10 = [i for i in range(10)] # tab10 est bien rangé par ordre croissant

# 3 est présent dans tab10
rep_vrai = dichotomie_iterative(3, tab10, len(tab10))

# 13 n'est pas présent dans tab10
rep_fausse = dichotomie_iterative(13, tab10, len(tab10))

print(rep_vrai, rep_fausse)
for i in range(len(tab10)):
    print(tab10[i], end = ' ')

True False
0 1 2 3 4 5 6 7 8 9

Algorithme récursif¶

Analyse

Récursion
- il faut appeler récursivement la recherche sur le sous-tableau (gauche ou droite) qui va bien
Terminaison : 2 cas
- on a trouvé la valeur cherchée
- le tableau est vide

Codage

Récursion : "le sous-tableau (gauche ou droite) qui va bien"

il faut pouvoir préciser les indices gauche et droit du sous-tableau traité
- donc paramètres formels : g et d
et sa taille (parce qu'on manipule un tableau)
- donc paramètre formel `n

def dichotomie(val, t, dim_t, g, d):
    '''recherche dichotomique : version récursive
    recherche val dans t[g, d] et retourne True ou False
    entrées. val : int, t: tableau d'int de taille n,
    g, d : int indices gauche et droite
    '''
    if g > d:
        return False # t est vide
    m = (g + d) // 2 
    if t[m] == val:
        return True
    elif val < t[m]: # val est dans la partie gauche
        dim_t = m - g 
        return dichotomie(val, t, dim_t, g, m-1)
    else:            # val est dans la partie droite
        dim_t = d - m
        return dichotomie(val, t, dim_t, m+1, d)
        
def dichotomie_recursive(val, t, dim_t):
    '''recherche dichotomique de val dans t de taille dim_t
    pour ressembler ) la version iterative en utilisant dichotomie
    '''
    return dichotomie(val, t, dim_t, 0, dim_t - 1)

'''appel de recherche dichotomique'''

#tab10 = [i for i in range(10)] # tab10 est bien rangé par ordre croissant

for i in range(len(tab10)):
    print(tab10[i], end = ' ' )
print()

# 3 est présent dans tab10
rep_vrai = dichotomie_recursive(3, tab10, len(tab10))

# 13 n'est pas présent dans tab10
rep_fausse = dichotomie_recursive(13, tab10, len(tab10))

print(rep_vrai, rep_fausse)

0 1 2 3 4 5 6 7 8 9 
True False

Remarque

Observer et bien comprendre pourquoi le traitement récursif (dichotomie) comporte 4 return
- Essayer par exemple de supprimer les 2 derniers
L'encapsulation de dichotomie dans dichotomie_recursive permet un appel de plus haut niveau similaire à la version itérative. Il n'est pas nécessaire : il contient lui-même l'appel principal de dichotomie.

Exercices

Instrumenter le code (ajouter des print() :) pour exhiber l'évalution de g, d et m
Effectuer les 2 recherches précédentes sans utiliser dichotomie_recursive mais seulement dichotomie

Les tours de Hanoi¶

Objectif¶

Déplacer l'empilement de disques du piquet gauche au piquet droit en respectant les règles suivantes :

déplacer un seul disque à la fois
un disque ne peut être posé que sur un disque de diamètre supérieur On doit utiliser le piquet du milieu.

début -> fin hanoi_debut /> hanoi_fin

/>

Solution récursive¶

Analyse¶

On note les piquets A, B, C de la gauche vers la droite. Départ = A, objectif = C
On note $n$ le nombre de disques à déplacer ; ici $n=4$
On veut donc résoudre le problème des tours de Hoanoi de taille 4 en allant de A vers C grâce à l'utilisation de B
- notons la résolution de ce problème Hanoi(4, A, C, B)
- plus généralement : Hanoi(n, départ, arrivée, intermédiaire)

Récursion
Si on déplace l'empilement complet avec les 3 disques supérieurs de A vers B en utilisant C (dur), ensuite on déplace le dernier (plus grand) disque de A vers C (facile), il ne reste qu'à déplacer l'empilement complet de 3 disques de B vers C en utilsant A (moins dur vu qu'on pu le faire à l'étape 1)

déplacer un empilement complet de 3 disques de A vers B (en utilisant C) = Hanoi(3, A, C, B)
déplacer le disque qui reste sur A vers C = Hanoi(1, A, C, B) ... oui: B ne sert à rien
déplacer un empilement complet de 3 disques de B vers C (en utilisant A) = Hanoi(3, B, C, A)

On tient la récursion ! 3 appels à `Hanoi` pour calculer `Hanoi` !!

Terminaison

quand tous les disques ont été déplacés, i.e. quand le piquet de départ est vide

Etape dure ... vraiment ?

NON : on "retombe" sur la résolution de Hanoi pour un nombre de disque diminué de 1 ...
ce qui devrait à un moment ne plus laisser aucun disque à déplacer :) On formalisera plus tard cette analyse de la terminaison de la solution récursive.

Codage¶

Yapluka !

def hanoi0(n, depart, arrivee, interm):
    '''tours de hanoi :  déplacer n disques de 
    depart vers arrivee en utilisant interm 
    (et en respectant les règles de déplacement du pb des tours de Hanoi)
    '''
    if n > 0:
        hanoi(n-1, depart, interm, arrivee)
        hanoi(1, depart, arrivee, interm)
        hanoi(n-1, interm, arrivee, depart)

''' resolution : appel '''
hanoi0(4, A, C, B)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
 in ()
      1 ''' resolution : appel '''
----> 2hanoi0(4, A, C, B)

NameError: name 'A' is not defined

Pour rendre effectif ce traitement,

il suffit d'indiquer les déplacements d'1 disque :
- hanoi(1, depart, arrivee, interm) = print(depart -> arrivee)
où les piquets sont les caractères : A, B, C

L'exécution de l'algo va donner tous les déplacements d'1 disque à appliquer au pb pour le résoudre

def hanoi(n, depart, arrivee, interm):
    '''affiche les déplacements pour déplacer n disques de 
    depart vers arrivee en utilisant interm 
    (et en respectant les règles de déplacement du pb des tours de Hanoi)
    '''
    if n > 0:
        hanoi(n-1, depart, interm, arrivee)
        print(depart, '-->', arrivee)
        hanoi(n-1, interm, arrivee, depart)        
        
'''appel'''
hanoi(4, 'A', 'C', 'B')

A --> B
A --> C
B --> C
A --> B
C --> A
C --> B
A --> B
A --> C
B --> C
B --> A
C --> A
B --> C
A --> B
A --> C
B --> C

ATTENTION : il y a 0 `return` et 1 `print` ... et pourtant l'algorithme termine et (semble) donner les déplacements qui résolvent le pb ... C'est un biais pédagogique introduit par la _modélisation_ des piquets par des caractères (difficile de faire autre chose que des `print` sur des caractères). Vous reprendrez cette résolution lorsque vous saurez représenter les empilements de disques par ... des piles.

''' appels simples pour se convaincre que ça marche et ...'''
hanoi(1, 'A', 'C', 'B')
print("---------")
hanoi(2, 'A', 'C', 'B')
print("---------")
hanoi(3, 'A', 'C', 'B')

A --> C
---------
A --> B
A --> C
B --> C
---------
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C

Exercice
Exécuter "à la main" les déplacements de hanoi(3)et hanoi(4) en numérotant les disques (1,2,3,...)e et les piquets (A,B,C)
et vérifier que les problèmes sont effectivement résolus !

Observation ... inquiétante¶

# disques	# déplacements
2	3
3	7
4	15

Normal ?

$n=1$ : OK pour hanoi(1) = 1 seul déplacement
$n=2$ : 3 appels à hanoi(1) donc $3\times1 = 3$
$n=3$ : 2 hanoi(2) + 1 hanoi(1) = $2\times 3 + 1 \times 1 = 7$
$n=4$ : 2 hanoi(3) + 1 hanoi(1) = $2\times 7 + 1 \times 1 = 15$

et ainsi de suite ...

ca augmente assez vite
on formalisera cette analyse de complexité dans un prochain chapitre.

Exercices

Coder un algo qui calcule le nombre de déplacements pour $n = 2, 3, \dots, 12$ et pour plus ensuite
Modifier hanoi() pour compter le nombre de déplacements total

a = 1
for i in range(1, 13):
    c = 2*a + 1
    print(i, ' -> ', c, 'déplacements')
    a = c
print("Ca vous fait penser à quelque chose :)")

1  ->  3 déplacements
2  ->  7 déplacements
3  ->  15 déplacements
4  ->  31 déplacements
5  ->  63 déplacements
6  ->  127 déplacements
7  ->  255 déplacements
8  ->  511 déplacements
9  ->  1023 déplacements
10  ->  2047 déplacements
11  ->  4095 déplacements
12  ->  8191 déplacements
Ca vous fait penser à quelque chose :)

A venir¶

Autres algorithmes récursifs importants
- avec des tableaux : tri fusion, tri rapide
Prouver la terminaison et la correction de ces algos récursifs
Etablir la complexité de ces algos récursifs
Dérécursifier : récursif -> itératif (quand on peut)