Pile d'appels

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

from turtle import *

def rectangle(n):
    """
    n - int, entier strictement positif
    """
    color('white', 'blue')
    begin_fill()
    for _ in range(2):
        forward(10)
        left(90)
        forward(n)
        left(90)
    end_fill()
    forward(10)


if __name__ == "__main__":
    TurtleScreen._RUNNING = True
    hideturtle()
    speed(0)
    rectangle(50)
    exitonclick()

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.

Exemple 1

On considère la fonction récursive suivante :

def fct1(n):
    """
    n - int
    """
    if n > 10:
        rectangle(n)
        fct1(n-10)

On effectue l'appel fct1(50). Quelle est la pile d'appel, et le tracé obtenu ?

Exemple 2

On échange les instructions de deux lignes pour définir la fonction récursive suivante :

def fct2(n):
    """
    n - int
    """
    if n > 10:
        fct2(n-10)
        rectangle(n)

On effectue l'appel fct1(50). Quelle est la pile d'appel, et le tracé obtenu ?

Détails

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)