Empiler les appels puis les dépiler au retour
Explication
À chaque appel récursif, un cadre est empilé, puis retiré lorsque l’appel se résout. Ce mécanisme permet de reconstituer le résultat final.
Deux fonctions s’appellent l’une l’autre pour déterminer le résultat
Explication
La récursivité mutuelle repose sur deux fonctions distinctes qui s’appellent alternativement. Dans l’exemple pair/impair, elles se relaient jusqu’aux cas de base.
s(n) = n + s(n-1) avec s(0) = 0
Explication
La somme récursive est définie par s(n) = n + s(n-1) et renvoie 0 quand n = 0. L’idée est d’ajouter le terme courant à la somme précédente.
Une fonction qui s’appelle elle-même dans son propre corps
Explication
Une fonction récursive se définit par un appel à elle-même à l’intérieur de son propre corps. Sans cet appel, il ne s’agit pas d’une récursivité.
a^n = a × a^(n-1) jusqu’à n = 0
Explication
La puissance récursive repose sur la relation a^n = a × a^(n-1) et s’arrête au cas n = 0. C’est ce qui permet de ramener progressivement le problème à un cas simple.
Le calcul rapide de la puissance avec test de parité et division par 2
Explication
L’exemple de puissance rapide utilise n % 2 pour distinguer les cas et n // 2 pour réduire le problème. Cette structure correspond à une récursivité multiple.
Stocker le résultat partiel jusqu’au cas d’arrêt
Explication
L’accumulateur conserve le résultat partiel et permet de renvoyer directement la valeur finale lorsque le cas d’arrêt est atteint. Il ne remplace pas la condition d’arrêt.
Un cas de base qui met fin aux appels
Explication
La condition d’arrêt, ou cas de base, stoppe la récursion et permet de renvoyer un résultat. Sans elle, les appels peuvent devenir infinis.
Le langage peut signaler une erreur de type Stack Overflow
Explication
Si la profondeur limite est dépassée, Python signale une erreur liée au dépassement de pile, souvent décrite comme Stack Overflow. Cela protège la pile d’exécution contre un excès d’appels imbriqués.
Le résultat est porté par un accumulateur au fil des appels
Explication
La récursivité terminale utilise un accumulateur qui transporte le résultat pendant les appels, sans calcul différé à la remontée. En récursivité non terminale, un calcul reste à faire après le retour.
Mémorisez les réponses avec 10 flashcards sur Principes et limites de la récursivité.
Principe de la récursivité — définition ?
Fonction qui s'appelle elle-même pour résoudre un problème.
Condition d’arrêt — rôle ?
Met fin à la récursion en renvoyant un résultat simple.
Exemple de fonction récursive — puissance ?
Calcule a^n en réduisant n jusqu’au cas de base n=0.
Consultez la fiche de révision complète sur Principes et limites de la récursivité.
Voir la fiche →Importe ton cours et l'IA génère des QCM avec corrections en 30 secondes.
Générateur de QCM