Pile d'appels

Pour illustrer les exemples de cette partie, nous allons utiliser la fonction rectangle() définie comme suit :

1
from turtle import *
2
3
def rectangle(n):
4
    """
5
    n - int, entier strictement positif
6
    """
7
    color('white', 'blue')
8
    begin_fill()
9
    for _ in range(2):
10
        forward(10)
11
        left(90)
12
        forward(n)
13
        left(90)
14
    end_fill()
15
    forward(10)
16
17
18
if __name__ == "__main__":
19
    TurtleScreen._RUNNING = True
20
    hideturtle()
21
    speed(0)
22
    rectangle(50)
23
    exitonclick()
24
Ordre des appels récursifs
Dans une fonction récursive, l'ordre d'exécution des instructions dépend des appels récursifs à la fonction. En d'autres termes, certaines instructions peuvent être exécutées immédiatement tandis que d'autres sont « mises en attente » dans une pile d'appels.
ExempleExemple 1
On considère la fonction récursive suivante :
1
def fct1(n):
2
    """
3
    n - int
4
    """
5
    if n > 10:
6
        rectangle(n)
7
        fct1(n-10)
8
On effectue l'appel fct1(50). Complétez, sur votre cahier, la pile d'appel puis tracez la figure correspondante.
Simulation
La correction est en bas de la page, mais on devrait obtenir, pour l'appel fct1(50), le dessin suivant :
ExempleExemple 2
On échange les instructions des lignes 22 et 23 pour définir la fonction récursive suivante :
1
def fct2(n):
2
    """
3
    n - int
4
    """
5
    if n > 10:
6
        fct2(n-10)
7
        rectangle(n)
8
On effectue l'appel fct2(50). Complétez, sur votre cachier, la pile d'appel puis tracez la figure correspondante.
Simulation
La correction est en bas de la page, mais on devrait obtenir, pour l'appel fct2(50), le dessin suivant :
Fondamental
Lorsqu'on exécute fct2(50) :
  • On exécute fct2(40) donc on met en attente rectangle(50) ;
  • On exécute fct2(30) donc on met en attente rectangle(40) en priorité devant rectangle(50) car fct2(40) doit être exécuté avant rectangle(50) ;
  • On exécute fct2(20) donc on met en attente rectangle(30) en priorité devant rectangle(40) en priorité devant rectangle(50) ;
  • On exécute fct2(10) donc on met en attente rectangle(20) en priorité devant rectangle(30) en priorité devant rectangle(40) en priorité devant rectangle(50) ;
  • 10 n'est pas strictement supérieur à 10, les appels se terminent.
  • On dépile par ordre de priorité en traçant dans l'ordre rectangle(20), rectangle(30), rectangle(40) puis rectangle(50)
RappelComplexité
La complexité d'un algorithme se décompose généralement sous deux formes :
  • La complexité en temps : combien de temps prend un algorithme pour s'exécuter ?
    On ramène généralement cette question au décompte du nombre d'opérations élémentaires nécessaires pour le déroulement de l'algorithme.
  • La complexité en mémoire : quel espace en mémoire est nécessaire au déroulement de l'algorithme ?
On notera généralement n le nombre de données à traiter. La complexité est ensuite donnée comme un « ordre de grandeur » de n. Cet ordre de grandeur est souvent noté O (se lit « grand O ») :
Classe de complexité
Type de complexité
O(1)
constante
O(log(n))
logarithmique
O(n)
linéaire
O(n × log(n))
quasi-linéaire
O(n²)
quadratique
O(2n)
exponentielle
O(n!)
factorielle
Pour les fonctions récursives envisagées ci-dessous, on admet que la complexité en temps est proportionnelle au nombre d'appels récursifs.
ExempleExemple 1
On considère la fonction récursive suivante :
1
def descente(n):
2
    """
3
    n - int
4
    """
5
    if n > 0:
6
        descente(n-1)
7
  1. Combien d'appels à la fonction descente() sont réalisés lorsqu'on exécute l'instruction descente(5) ?
  2. Combien d'appels à la fonction descente() sont réalisés lorsqu'on exécute l'instruction descente(8) ?
  3. Donnez, en fonction de n, le nombre d'appels à la fonction descente() réalisés lorsqu'on exécute l'instruction descente(n).
  4. En déduire la complexité de cette fonction.
Des élèments de réponses sont en fin de page...
ExempleExemple 2
On considère la fonction récursive suivante :
1
def piano(n):
2
    """
3
    n - int
4
    """
5
    if n > 0:
6
        piano(n-1)
7
        piano(n-1)
8
  1. Combien d'appels à la fonction piano() sont réalisés lorsqu'on exécute l'instruction piano(3) ?
  2. Combien d'appels à la fonction piano() sont réalisés lorsqu'on exécute l'instruction piano(5) ?
  3. Donnez, en fonction de n, le nombre d'appels à la fonction piano() réalisés lorsqu'on exécute l'instruction piano(n).
  4. En déduire la complexité de cette fonction.
Éléments de réponses...
Voici les éléments de réponses des exemples données ci-dessus.
Ordre des appels récursifs
SimulationExemple 1 : fct1()
Le programme complet :
1
from turtle import *
2
3
def rectangle(n):
4
    """
5
    n - int, entier strictement positif
6
    """
7
    color('white', 'blue')
8
    begin_fill()
9
    for _ in range(2):
10
        forward(10)
11
        left(90)
12
        forward(n)
13
        left(90)
14
    end_fill()
15
    forward(10)
16
17
def fct1(n):
18
    """
19
    n - int
20
    """
21
    if n > 10:
22
        rectangle(n)
23
        fct1(n-10)
24
25
if __name__ == "__main__":
26
    TurtleScreen._RUNNING = True
27
    hideturtle()
28
    speed(0)
29
    fct1(50)
30
    exitonclick()
31
Le rectangle est tracé avant l'appel récursif suivant :
SimulationExemple 2 : fct2()
Le programme complet :
1
from turtle import *
2
3
def rectangle(n):
4
    """
5
    n - int, entier strictement positif
6
    """
7
    color('white', 'blue')
8
    begin_fill()
9
    for _ in range(2):
10
        forward(10)
11
        left(90)
12
        forward(n)
13
        left(90)
14
    end_fill()
15
    forward(10)
16
17
def fct2(n):
18
    """
19
    n - int
20
    """
21
    if n > 10:
22
        fct2(n-10)
23
        rectangle(n)
24
25
if __name__ == "__main__":
26
    TurtleScreen._RUNNING = True
27
    hideturtle()
28
    speed(0)
29
    fct2(50)
30
    exitonclick()
31
Lorsqu'on exécute fct2(50) :
  • On exécute fct2(40) donc on met en attente rectangle(50) ;
  • On exécute fct2(30) donc on met en attente rectangle(40) en priorité devant rectangle(50) car fct2(40) doit être exécuté avant rectangle(50) ;
  • On exécute fct2(20) donc on met en attente rectangle(30) en priorité devant rectangle(40) en priorité devant rectangle(50) ;
  • On exécute fct2(10) donc on met en attente rectangle(20) en priorité devant rectangle(30) en priorité devant rectangle(40) en priorité devant rectangle(50) ;
  • 10 n'est pas strictement supérieur à 10, les appels se terminent.
  • On dépile par ordre de priorité en traçant dans l'ordre rectangle(20), rectangle(30), rectangle(40) puis rectangle(50)
L'illustration ci-dessous permet de mieux visualiser l'empilement de ces appels :
Complexité
SimulationExemple 1
La flèche « → » modélise l'appel suivant.
  1. descente(5) → descente(4) → descente(3) → descente(2) → descente(1) → descente(0) (0 n'est pas strictement supérieur à 0, c'est le dernier appel récursif).
    Lorsqu'on exécute l'instruction descente(5), on effectue 6 appels à la fonction descente().
  2. De la même manière, lorsqu'on exécute l'instruction descente(8), on effectue 9 appels à la fonction descente().
  3. Soit n est négatif ou nul, alors le test n > 0 n'est pas validé et il n'y a pas d'appel récursif à la fonction descente().
    Soit n est strictement positif. Les appels se déroulent alors ainsi :
    descente(n) → descente(n-1) → ... → descente(1) → descente(0).
    On effectue donc n+1 appels récursifs à la fonction descente().
  4. Ce nombre d'appels est un multiple de n : la complexité est linéaire.
SimulationExemple 2
  1. piano(3) appelle deux fois piano(2)
    Chaque appel de piano(2) appelle deux fois piano(1).
    Chaque appel de piano(1) appelle deux fois piano(0).
    Chaque appel de piano(0) termine car 0 n'est pas strictement supérieur à 0.
    Le nombre total d'appels générés par piano(3) est donc \(1+2+4+8=2⁴−1\)
  2. De la même manière, lorsqu'on exécute l'instruction piano(5), on effectue \(2⁶−1\) appels à la fonction piano().
  3. Soit n est négatif ou nul, alors le test n > 0 n'est pas validé et il n'y a pas d'appel récursif à la fonction piano().
    Soit n est strictement positif. On note \(T(n)\) le nombre d'appels engendrés par l'exécution de piano(n). Dès lors, \(T(n)=2T(n−1)=2×2T(n−2)=⋯=2^n T(0)\) appels.
    On effectue donc \(2^n\) appels piano(0). Le nombre total d'appels engendrés par piano(n) est \(1+2^1+2^2+...+2^n=2^{n+1}−1\)
  4. Ce nombre d'appels est, à une constante près, une puissance n-ième de 2 donc la complexité est exponentielle.