Lernzettel: Principes et limites de la récursivité

📋 Plan du Cours

1. Principe de la récursivité
2. Exemples de fonctions récursives
3. Récursivité terminale et itérative
4. Récursivité multiple et mutuelle
5. Pile d'exécution et limites

📖 1. Principe de la récursivité

🔑 Notions clés & Définitions

• Fonction récursive : Une fonction récursive se définit en s’appelant elle-même, à l’intérieur de son propre corps.
• Condition d’arrêt : Une condition d’arrêt est un cas de base qui met fin aux appels récursifs et permet de renvoyer un résultat.
• État trivial : Un état trivial est un cas simple directement calculable qui sert de base à la terminaison de la récursion.

📝 Points essentiels

• Un algorithme récursif s’appelle lui-même pour progresser vers un cas simple.
• Sans condition d’arrêt, la récursion peut produire des appels infinis et provoquer une erreur.
• Une définition récursive efficace conduit vers un état d’arrêt afin d’éviter l’infinité des appels.

💡 Astuce mémo

Récursivité = appel soi-même + cas simple qui coupe le cycle.

📖 2. Exemples de fonctions récursives

🔑 Notions clés & Définitions

• puissance : La puissance récursive calcule $a^n$ en réduisant $n$ vers un cas de base où le résultat est directement renvoyé.
• Somme des n premiers termes : La somme récursive calcule $0+1+\dots+n$ en ajoutant le terme courant à la somme de $n-1$.
• puissance récursive : L’approche récursive du calcul de $a^n$ utilise la relation $a^n=a\cdot a^{n-1}$ jusqu’au cas $n=0$.

📝 Points essentiels

• Pour $a^n$ avec $n>0$, le cas de base est $n=0$ et la valeur renvoyée est $1$.
• Dans l’exemple, $n$ décroît à chaque appel via $n-1$, ce qui atteint bien la condition d’arrêt.
• La version non récursive de la somme utilise une boucle de $i\in[0,n]$ et cumule dans une variable $s$.
• La somme récursive de $n$ suit $s(n)=n+s(n-1)$ et renvoie $0$ quand $n=0$.
• La profondeur peut atteindre la limite en Python : l’exemple mentionne une limite à 1000 récursions par défaut.

💡 Astuce mémo

Puissance : $n\to n-1$ jusqu’à $n=0$ ; Somme : on cumule vers $0$.

📖 3. Récursivité terminale et itérative

🔑 Notions clés & Définitions

• Récursivité non terminale : Une récursivité non terminale laisse des calculs en attente, puis les effectue en remontant depuis le cas de base.
• Récursivité terminale : Une récursivité terminale utilise un accumulateur pour porter le résultat au fil des appels, sans calcul différé à la remontée.
• Accumulateur : Un accumulateur est un argument qui stocke le résultat partiel et permet de renvoyer directement la valeur finale au cas d’arrêt.

📝 Points essentiels

• Dans une fonction non terminale, on calcule du type $n+somme\_rec(n-1)$, donc une opération reste à faire après le retour récursif.
• Une fonction récursive terminale fait avancer un accumulateur à chaque étape et renvoie l’accumulateur au moment où $n=0$.
• L’exemple terminal utilise $sommeRecTerm(n,acc=0)$ et ajoute $n$ à $acc$ dans l’appel récursif, puis renvoie $acc$ au cas de base.
• Python peut imposer une limite d’appels récursifs, l’exemple cite 2700 sur Capytale en console en ligne.
• On peut modifier la limite avec $sys.getrecursionlimit()$ et $sys.setrecursionlimit(10000)$.

💡 Astuce mémo

Terminale = accumulateur qui porte la réponse, donc pas de calcul à “remonter”.

📖 4. Récursivité multiple et mutuelle

🔑 Notions clés & Définitions

• Récursivité multiple : La récursivité multiple fait intervenir plusieurs formules ou réductions internes, souvent en combinant opérations et récursions selon la structure du problème.
• Double récursion : La double récursion est une récursion où une fonction appelle deux fois elle-même sur des arguments différents, comme pour Fibonacci.
• Récursivité mutuelle : La récursivité mutuelle définit deux fonctions qui s’appellent l’une l’autre pour déterminer un résultat.

📝 Points essentiels

• L’exemple de puissance utilise une séparation selon la parité de $n$ via $n\%2==0$ pour réduire le problème en divisant par 2 avec $n//2$.
• La réduction par division entière // fait atteindre $0$ plus vite que $n\to n-1$, ce qui correspond à une complexité logarithmique $O(log(n))$.
• La suite de Fibonacci est donnée par $Fib(n)=Fib(n-1)+Fib(n-2)$ pour $n>1$, donc elle nécessite deux appels récursifs.
• La récursivité mutuelle pair/impair alterne les appels pair(n) et impair(n-1) jusqu’à $pair(0)$ et impair(0).
• L’exemple McCarthy 91 utilise $M(n)=n-10$ si $n>100$ et $M(M(n+11))$ si $n\le 100$.

💡 Astuce mémo

Multiple/double : pense “parité” ou “deux appels” ; mutuelle : pense “deux fonctions qui se relais”.

📖 5. Pile d'exécution et limites

🔑 Notions clés & Définitions

• Pile d’exécution : La pile d’exécution est une structure où les appels récursifs sont empilés puis dépilés pour reconstituer le résultat final.
• Stack Overflow : Stack Overflow est l’erreur due au dépassement de la profondeur maximale autorisée pour la pile d’exécution en récursivité.
• Profondeur maximale : La profondeur maximale est la limite de nombre d’appels imbriqués avant que le langage n’arrête l’exécution pour protéger la pile.

📝 Points essentiels

• À chaque appel récursif, un “cadre” est empilé, puis dépilé quand l’appel se résout, jusqu’au résultat final.
• L’exemple a^n illustre l’empilement : $expo(2,3)$ dépend de $expo(2,2)$, puis de $expo(2,1)$, puis de $expo(2,0)$.
• Le surcoût mémoire vient du fait que la pile peut devenir gourmande avec de nombreux appels récursifs.
• Si on dépasse la profondeur limite, Python signale “Stack Overflow” avec une profondeur maximum dépassée.
• Le test expo(2,1000) illustre l’impact de la profondeur avant de réussir à produire le résultat.

💡 Astuce mémo

Pile = empiler à l’appel, dépiler au retour ; trop d’étages = Stack Overflow.

📊 Tableaux de synthèse

Non terminale vs terminale

⚠️ Pièges & confusions fréquents

1. Penser que la condition d’arrêt n’est pas nécessaire : sans cas de base, la récursion peut ne jamais s’arrêter.
2. Confondre non terminale et terminale : dans la non terminale, le calcul n’est pas fini avant le retour récursif.
3. Oublier que $n$ doit évoluer vers l’arrêt : une mauvaise modification peut empêcher l’atteinte de $n=0$.
4. Croire que récursif et itératif sont toujours identiques : l’exemple rappelle que cela dépend du langage et du problème.
5. Rater la différence entre $n-1$ et $n//2$ : le premier réduit linéairement, le second peut mener à une réduction logarithmique.
6. Dépasser la limite Python : trop d’appels peut provoquer “Stack Overflow”.

✅ Checklist Examen

1. Définir ce qu’est une fonction récursive et expliquer l’idée d’appel à elle-même.
2. Identifier les éléments indispensables : condition d’arrêt et état trivial garantissant la terminaison.
3. Pour le calcul de $a^n$, donner le cas de base $n=0$ et la relation utilisée pour $n>0$.
4. Expliquer pourquoi la version récursive de la puissance termine quand $n$ décroît vers 0.
5. Écrire la logique de la somme $0+1+...+n$ en version récursive avec le cas $n=0$ et la relation avec $n-1$.
6. Distinguer récursivité non terminale et récursivité terminale via la notion de calcul en attente ou non.
7. Décrire le principe de l’accumulateur et savoir comment il change la forme de la fonction (renvoi direct à l’arrêt).
8. Rappeler l’exemple terminal de sommeRecTerm et comment $acc$ évolue à chaque appel.
9. Reconnaître une récursivité par parité (cas pair/impair) et l’usage de $n$ et $n//2$ dans l’exemple de puissance rapide.
10. Expliquer pourquoi la réduction par division entière peut donner une complexité logarithmique $O(log(n))$ dans l’exemple.
11. Donner la forme de Fibonacci pour $n>1$ et préciser qu’il y a double appel récursif.
12. Décrire la différence entre récursivité mutuelle et récursion simple à partir de pair/impair.
13. Expliquer le rôle de la pile d’exécution dans le déroulement empilement puis dépilement des appels récursifs.
14. Citer la limite pratique évoquée pour Python et le risque associé, y compris “Stack Overflow”.