La récursivité (oe)

La récursivité en algorithmique est le fait qu'un algorithme contienne un ou plusieurs appels de lui-même.

def fctA():
    print ("Début fonction fctA")
    i=0
    while i<5:
        print(f"fctA {i}")
        i = i + 1
    print ("Fin fonction fctA")
def fctB():
    print ("Début fonction fctB")
    i=0
    while i<5:
        if i==3:
            fctA()
            print("Retour à la fonction fctB")
        print(f"fctB {i}")
        i = i + 1
    print ("Fin fonction fctB")
 
fctB()

La fonction fctB appelle la fonction fctA, lors de son exécution, la fonction fctA va interrompre la fonction fctB.

Pour gérer ces fonctions qui appellent d'autres fonctions, le système utilise une pile d'exécution.
La pile d'exécution permet d'enregistrer les informations sur les fonctions en cours d'exécution dans un programme.

La fonction au sommet est la fonction en cours d'exécution, elle met donc en “pause” les autres fonctions, comme c'est une pile, elle se base sur le principe du First In, Last out (le dernier à rentrer sera le premier à sortir).
Une fois qu'une fonction à terminé son exécution, elle sortira, on dit qu'elle est dépilée.

def fonct(n):
    if n>0:
        fonct(n-1)
    print(n)
 
fonct(3)

Cette fonction est une fonction récursive (elle s'appelle elle-même), elle va énumérer les nombres de 0 jusqu'à 3.

Mais comment cette fonction fonctionne-t-elle? Voyons voir sa pile d'exécution.