Fiche de révision : Récursivité et pile d’exécution

📋 Plan du Cours

1. Pile d’exécution et appels de fonctions
2. Variables locales et reprise d’exécution
3. Principe des fonctions récursives
4. Exemples de calculs récursifs
5. Schéma général et compromis récursifs
6. Paradigme fonctionnel

📖 1. Pile d’exécution et appels de fonctions

★ À maîtriser

• Lorsqu’une fonction appelle une autre fonction, elle s’exécute jusqu’à l’appel, se met en pause pendant l’exécution de la fonction appelée, puis reprend à sa fin.

• La fonction au sommet de la pile d’exécution est celle qui est en cours d’exécution, tandis que les fonctions situées en dessous sont en pause.

Compléments

• La pile d’exécution enregistre des informations sur les fonctions en cours d’exécution, qui s’empilent les unes sur les autres.

• Quand une fonction termine son exécution, elle est automatiquement retirée du sommet de la pile ; cette opération s’appelle le dépilement.

💡 Astuce mémo

Visualiser les fonctions empilées : seule celle du sommet agit, les autres attendent.

📖 2. Variables locales et reprise d’exécution

★ À maîtriser

• La valeur d’une variable locale de la fonction appelante est conservée pendant l’exécution d’une autre fonction, même si celle-ci utilise une variable locale portant le même nom.

Compléments

• La pile d’exécution conserve l’adresse mémoire de la prochaine instruction machine à exécuter lorsque la fonction en pause reprendra.

📖 3. Principe des fonctions récursives

🔑 Notions clés & Définitions

• Fonction récursive : Fonction qui peut s’appeler elle-même au cours de son exécution.

📝 Points essentiels

• Les appels récursifs de fonctions sont permis par la plupart des langages de programmation.

• La récursivité apparaît notamment dans :

  • les suites récurrentes en mathématiques
  • les géométries fractales en mathématiques
  • la mise en abyme en littérature

📖 4. Exemples de calculs récursifs

🔑 Notions clés & Définitions

• Factorielle : La factorielle de n vérifie $n! = 1$ si n=1 et $n! = n \times (n-1)!$ si n>1.
• Suite récurrente : La suite considérée vérifie $u_0 = \frac{1}{2}$ et $u_{n+1} = u_n(1-u_n)$ pour tout entier naturel n.
• Suite de Fibonacci : La suite de Fibonacci vérifie $u_0=0$, $u_1=1$ et $u_{n+2}=u_{n+1}+u_n$ pour tout entier naturel n.

★ À maîtriser

• Le calcul récursif de la factorielle s’arrête au cas n=1, qui renvoie 1 ; pour n>1, il renvoie n multiplié par la factorielle de n−1.

• 🔄 Le calcul récursif de Fibonacci suit ces cas :

  1. Si n=0, renvoyer 0.
  2. Si n=1, renvoyer 1.
  3. Sinon, renvoyer la somme de Fibonacci(n−1) et de Fibonacci(n−2).

Compléments

• Le calcul récursif du terme de rang n de la suite renvoie 1/2 si n=0 et, sinon, le terme de rang n−1 multiplié par un moins ce terme.

📖 5. Schéma général et compromis récursifs

★ À maîtriser

• Une fonction récursive suit un schéma comportant un cas d’arrêt sans appel récursif et un autre cas où une instruction peut faire intervenir la fonction récursive.

• La gestion de la pile peut provoquer un débordement, ralentir considérablement l’exécution et rendre l’efficacité de la fonction difficile à maîtriser.

Compléments

• La récursivité permet généralement de résoudre élégamment des problèmes compliqués, évite d’entrer dans le détail de l’exécution et convient particulièrement à certaines structures de données comme les arbres.

• Toute fonction récursive peut être transformée en version itérative, et réciproquement ; le choix dépend du contexte.

💡 Astuce mémo

La récursivité rend le code plus élégant, mais la pile peut le ralentir ou déborder.

📖 6. Paradigme fonctionnel

★ À maîtriser

📌 Le paradigme fonctionnel privilégie l’utilisation des fonctions, contrairement au paradigme impératif utilisé jusque-là.

• Dans un langage purement fonctionnel, tout est fonction et aucune affectation n’est possible.

Compléments

• Les langages fonctionnels présentent notamment l’avantage d’optimiser la récursivité.

💡 Astuce mémo

Impératif : affectations ; fonctionnel pur : tout est fonction, sans affectation.