NSI · TERMINALELa récursivitéune fonction qui s'appelle elle-mêmeDÉFINIRDeux cas, toujoursdef fact(n): if n == 0: # cas de base return 1 return n * fact(n - 1) # cas récursifCAS DE BASEune réponse directe : il arrête les appelsCAS RÉCURSIFla même question, sur un problème plus petit5! = 5 × 4!LA PILE D'APPELSfact(4), pas à pasON DESCEND : CHAQUE APPEL ATTENDON REMONTEfact(4) = 4 × fact(3)→ 24fact(3) = 3 × fact(2)→ 6fact(2) = 2 × fact(1)→ 2fact(1) = 1 × fact(0)→ 1fact(0) = 1→ 1fact(4) = 4 × 3 × 2 × 1 = 24LE DANGERSans cas de basedef f(n): return f(n + 1) # aucun arrêtf(0)f(1)f(2)f(3)f(4)f(5)f(6)f(7)la pile grandit…RecursionError:maximum recursiondepth exceededPython s'arrête au-delà d'une profondeurmaximale : sys.getrecursionlimit().COMPARERRécursif ou itératifRÉCURSIFdef fact(n): return 1 if n == 0 else n * fact(n - 1)ITÉRATIFdef fact(n): r = 1 for k in range(2, n + 1): r = r * k return rMême résultat. La boucle n'empile rien :sa mémoire ne grandit pas avec n.Le récursif suit la définition ; l'itératif économise la pile.QUAND ELLE S'IMPOSEUne structure récursivedef taille(a): if a is None: return 0 return 1 + taille(a.gauche) + taille(a.droit)ABCDE11315taille = 5Un arbre, c'est une racine et deux sous-arbres :la fonction a la forme même de la donnée.De même, le tri fusion trie deux moitiés, récursivement.LE PIÈGERecalculer sans findef fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2)f1f0f2f1f3f1f0f2f4f1f0f2f1f3f515 appelsfib(30) :2 692 537 appelsavec @functools.cache :31 appelsMémoriser les résultats : la programmation dynamique.À RETENIRDeux casun cas de base qui arrête, un cas récursifqui réduit le problèmeLa pile d'appelschaque appel attend le suivant ;sans cas de base, RecursionErrorRécursif ou itératifmême résultat ; la boucle n'empile rienet sa mémoire ne grandit pasBien l'employerarbres, diviser pour régner ;mémoriser les appels répétésJLjeromelabbe.frFiches de connaissance · NSI, TerminaleJL