Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== La récursivité (oe) ======

La **récursivité** en algorithmique est le fait qu'un algorithme contienne un ou plusieurs appels de lui-même. \\ \\ \\ \\ 
{{  :les_fiches_revisions:fonction_recursive.png?200|}}
{{ :les_fiches_revisions:langages_programmation:recursivite.png?500 |}}
\\ \\ \\
===== La pile d'exécution =====

{{  :les_fiches_revisions:langages_programmation:recur_resultat.png?200|}}
<code python>
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()
</code>

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

{{:les_fiches_revisions:langages_programmation:pile_d_execution_2.png?300 |}} \\ \\ 
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**.

\\ \\ \\ \\ 

===== Les fonctions récursives =====

{{  :les_fiches_revisions:langages_programmation:resultat_recur_2.png?400|}}
<code python>
def fonct(n):
    if n>0:
        fonct(n-1)
    print(n)

fonct(3)
</code>
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.
{{ :les_fiches_revisions:langages_programmation:pile_recur.png?800 |}}