Récursivité, calculabilité et décidabilité

Récursivité : cas de base et cas récursif#

Basiseduscol-programme-nsi-terminale

Définition récursive de la factorielle : descente vers le cas de base

Fig. 1Descente : chaque appel se ramène à un appel plus petit, jusqu'au cas de base fact(0) = 1 (mis en évidence). Puis la remontée multiplie : 1, ×1, ×2, ×3, ×4 = 24.

Une fonction est RÉCURSIVE lorsqu'elle s'appelle elle-même dans sa propre définition. Elle exprime la solution d'un problème en fonction de la solution du même problème sur une entrée PLUS PETITE.

Toute fonction récursive correcte comporte deux parties : un (ou plusieurs) CAS DE BASE, résolu directement sans appel récursif, et un (ou plusieurs) CAS RÉCURSIF, qui se ramène à un cas plus proche du cas de base.

Exemple canonique, la factorielle : 0! = 1 (cas de base) et n! = n × (n−1)! pour n ⩾ 1 (cas récursif). De même la somme 1+2+...+n, une suite définie par récurrence, ou la recherche dichotomique récursive sur un tableau trié.

Une définition récursive se LIT comme une définition par récurrence mathématique : le cas de base correspond à l'initialisation, le cas récursif à la relation de passage du rang précédent au rang courant.

Rappel de première : on sait déjà écrire des fonctions avec des boucles ; la terminale ajoute le schéma récursif. Beaucoup de problèmes récursifs (factorielle, somme) ont aussi une version itérative équivalente, mais certains s'écrivent bien plus naturellement par récursivité (parcours d'arbres, diviser-pour-régner).

La récursivité TERMINALE (où l'appel récursif est la toute dernière opération) n'est PAS au programme de NSI : on reste sur le schéma général cas de base / cas récursif et sur l'analyse par la pile d'appels.

n! = \begin{cases} 1 & \text{si } n = 0 \quad (\text{cas de base}) \\ n \times (n-1)! & \text{si } n \geqslant 1 \quad (\text{cas récursif}) \end{cases}

Définition récursive de la factorielle

Le cas de base 0! = 1 arrête la descente ; le cas récursif ramène le calcul de n! à celui de (n−1)!, plus proche du cas de base.

\operatorname{somme}(n) = \begin{cases} 0 & \text{si } n = 0 \\ n + \operatorname{somme}(n-1) & \text{si } n \geqslant 1 \end{cases}

Somme 0+1+...+n par récurrence

Même schéma : initialisation à 0, puis on ajoute n à la somme jusqu'à n−1.

Exemple corrigé

Écrire et vérifier somme(n)

Écrire une fonction récursive somme(n) qui renvoie 0+1+2+...+n pour un entier n ⩾ 0. Préciser le cas de base et le cas récursif, puis calculer somme(4) en déroulant les appels.

Identifier le cas de base
Pour n = 0, la somme vaut 0 : on renvoie 0 directement, sans appel récursif.
Écrire le cas récursif
Pour n ⩾ 1, la somme de 0 à n vaut n plus la somme de 0 à n−1. En Python : def somme(n): return 0 if n == 0 else n + somme(n-1).
Dérouler somme(4)
On descend : somme(4) = 4 + somme(3) = 4 + 3 + somme(2) = 4 + 3 + 2 + somme(1) = 4 + 3 + 2 + 1 + somme(0).
Atteindre le cas de base et remonter
somme(0) = 0 arrête la descente ; on remonte en additionnant : 0 → 1 → 3 → 6 → 10.

Résultat : somme(4) = 10. Le cas de base est somme(0) = 0 ; le cas récursif est somme(n) = n + somme(n−1).

Erreurs fréquentes

Oublier le cas de base (ou le placer après l'appel récursif) : la fonction s'appelle alors indéfiniment et provoque un dépassement de la pile d'appels (RecursionError en Python).
Écrire un cas récursif qui ne se rapproche pas du cas de base (par exemple appeler f(n) au lieu de f(n−1)) : la valeur n'« avance » jamais vers le cas de base.
Confondre n × (n−1)! avec (n × (n−1))! : la factorielle ne porte que sur (n−1).

Révision active

Écrire une fonction récursive somme(n) qui renvoie 0+1+2+...+n pour un entier n ⩾ 0. Préciser le cas de base et le cas récursif, puis vérifier le résultat à la main pour n = 4.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

La pile d'appels : exécuter et tracer une fonction récursive#

Standardeduscol-programme-nsi-terminale

Arbre des appels de fib(5) : 15 appels, recouvrements et coût exponentiel

Fig. 2fib(5) naïf déclenche 15 appels : les mêmes sous-problèmes (fib(3), fib(2), fib(1)) sont recalculés de nombreuses fois. Le nombre d'appels croît comme une exponentielle — d'où l'intérêt de la mémoïsation.

À l'exécution, chaque appel de fonction non encore terminé est mémorisé dans la PILE D'APPELS : on y empile, à la descente, un cadre (frame) contenant les paramètres et l'endroit où reprendre ; on dépile à la remontée, quand l'appel renvoie sa valeur.

La pile d'appels fonctionne en LIFO (Last In, First Out, « dernier entré, premier sorti ») : c'est exactement la structure de données « pile ». La récursivité et la structure de pile sont donc directement liées.

Pour un appel récursif, on empile un cadre à chaque descente jusqu'au cas de base ; ce dernier ne fait pas d'appel récursif et déclenche le dépilement, qui combine les résultats partiels de bas en haut.

La PROFONDEUR de récursion est le nombre maximal de cadres empilés simultanément (pour fact(n), elle vaut n+1). Une profondeur trop grande (ou infinie) dépasse la taille de la pile : c'est le dépassement de pile (stack overflow / RecursionError).

Tracer une récursion = écrire la suite des appels empilés à la descente, repérer le cas de base, puis écrire les valeurs renvoyées à la remontée. C'est la méthode demandée pour « analyser le fonctionnement d'un programme récursif ».

Attention au coût : l'appel récursif naïf de Fibonacci recalcule un même fib(k) de très nombreuses fois (fib(5) déclenche 15 appels). L'arbre des appels grossit de façon EXPONENTIELLE — la pile, elle, reste de profondeur linéaire.

\text{profondeur de pile pour } \operatorname{fact}(n) = n + 1

Profondeur de la pile (factorielle)

Les cadres fact(n), fact(n−1), ..., fact(0) sont empilés simultanément au moment où le cas de base est atteint : il y en a n+1.

A(n) = \begin{cases} 1 & \text{si } n \leqslant 1 \\ 1 + A(n-1) + A(n-2) & \text{si } n \geqslant 2 \end{cases} \quad\Rightarrow\quad A(5) = 15

Nombre total d'appels de fib naïf

A(n) compte les appels : un pour l'appel courant, plus ceux des deux sous-appels. On vérifie A(5) = 15 ; ce nombre croît exponentiellement.

Croissance du nombre d'appels : fib naïf (exponentiel) contre approche linéaire

Exemple corrigé

Tracer la pile d'appels de fact(4)

On exécute fact(4) avec fact(0)=1 et fact(n)=n*fact(n-1). Décrire l'évolution de la pile d'appels (descente puis remontée) et donner la profondeur maximale atteinte ainsi que le résultat.

Empiler à la descente
On empile successivement, dans cet ordre : fact(4), fact(3), fact(2), fact(1), fact(0). Chacun attend la valeur de l'appel qu'il a déclenché.
Atteindre le cas de base
fact(0) renvoie 1 sans nouvel appel : la descente s'arrête. La pile contient alors 5 cadres simultanément.
Dépiler à la remontée
On combine de bas en haut : fact(1) = 1×1 = 1, fact(2) = 2×1 = 2, fact(3) = 3×2 = 6, fact(4) = 4×6 = 24. Chaque dépilement libère un cadre.
Conclure
La pile est vide une fois fact(4) renvoyé. Le nombre d'appels (5) est ici égal à la profondeur car la récursion est linéaire (un seul appel par cadre).

Résultat : fact(4) = 24 ; profondeur maximale de la pile = 5 cadres (fact(4) à fact(0)).

Schritt-für-Schritt Erklärung5 Schritte

1
Une fonction récursive ne s'exécute pas par magie : chaque appel non terminé est rangé dans la pile d'appels. Suivons fact(4).
2
À la descente, on empile fact(4), puis fact(3), fact(2), fact(1) et enfin fact(0). Chaque cadre attend le résultat de l'appel suivant.
3
fact(0) vaut 1 : c'est le cas de base. Il arrête la descente et déclenche le dépilement.
4
On remonte en multipliant : 1, puis 1, 2, 6 et 24. La pile se vide du sommet vers la base.
5
Retenez la distinction : la profondeur de la pile vaut n+1, mais le nombre TOTAL d'appels peut exploser, comme pour fib où il croît exponentiellement.

Erreurs fréquentes

Croire que tout l'arbre des appels est dans la pile en même temps : non. La pile ne contient que la BRANCHE en cours de descente (profondeur), pas l'arbre entier.
Confondre nombre total d'appels (taille de l'arbre, ici 15 pour fib(5)) et profondeur maximale de la pile (ici 5).
Oublier que chaque appel a ses propres variables locales : les n de fact(3) et fact(2) sont des copies distinctes, empilées séparément.

Révision active

Pour la fonction fib définie par fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2), dessiner l'arbre des appels de fib(4) et compter le nombre total d'appels. Comparer ce nombre à la profondeur maximale de la pile.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Terminaison d'une fonction récursive#

Standardeduscol-programme-nsi-terminale

Terminaison : un variant entier décroît strictement vers le cas de base

Fig. 4Un variant entier (ici n) décroît strictement (d'au moins 1) à chaque appel tout en restant positif ou nul : il atteint le cas de base 0 (mis en évidence) en un nombre fini d'étapes. C'est ce qui garantit la TERMINAISON.

Une fonction récursive TERMINE si tout appel finit par atteindre un cas de base après un nombre FINI d'appels. Sinon, la récursion est infinie et provoque un dépassement de pile.

Méthode de référence : exhiber un VARIANT, c'est-à-dire une quantité entière positive (ou nulle) associée à chaque appel, qui DÉCROÎT STRICTEMENT d'un appel à l'appel récursif suivant. Une suite d'entiers positifs strictement décroissante est finie : elle atteint donc le cas de base.

Pour fact(n) et somme(n), le variant est n lui-même : il passe de n à n−1 à chaque appel, reste ⩾ 0, et atteint 0 (le cas de base) en exactement n étapes.

Pour la recherche dichotomique récursive, le variant est la longueur de l'intervalle de recherche, qui est (au moins) divisée par deux à chaque appel et finit par atteindre 0 ou 1 (cas de base).

Justifier la terminaison ≠ justifier la correction. La terminaison dit que la fonction s'arrête ; la correction dit qu'elle renvoie la bonne valeur. Le programme exige seulement de JUSTIFIER LA TERMINAISON pour ce thème.

Attention : un variant doit décroître à CHAQUE appel récursif et rester minoré (par 0). Si la valeur peut stagner ou croître (ex. appeler f(n) ou f(n+1) dans un cas), rien ne garantit l'arrêt.

v_0 > v_1 > v_2 > \cdots \geqslant 0 \ \text{(entiers)} \ \Longrightarrow\ \text{suite finie}

Principe du variant

Une suite d'entiers positifs strictement décroissante ne peut pas être infinie ; elle atteint donc nécessairement le cas de base.

\text{pour } \operatorname{fact}(n) : \quad v(\operatorname{fact}(n)) = n,\qquad n \to n-1,\qquad n \geqslant 0

Variant de la factorielle

Le variant n décroît de 1 à chaque appel et reste positif ; il atteint 0 en n appels, ce qui prouve la terminaison.

Exemple corrigé

Justifier la terminaison de pgcd (algorithme d'Euclide récursif)

On considère pgcd(a, b) : si b = 0, renvoyer a ; sinon, renvoyer pgcd(b, a mod b), avec a et b entiers naturels. Justifier que cette fonction récursive termine.

Choisir un variant
On prend pour variant le second argument b, qui est un entier naturel (⩾ 0) à chaque appel.
Montrer la décroissance stricte
À l'appel récursif pgcd(b, a mod b), le nouveau second argument est a mod b. Or, par définition du reste, on a toujours 0 ⩽ a mod b < b lorsque b > 0. Le variant passe donc de b à une valeur STRICTEMENT plus petite.
Conclure par le principe du variant
Le variant b est un entier positif qui décroît strictement à chaque appel récursif ; une telle suite est finie et atteint nécessairement 0.
Atteindre le cas de base
Quand le variant atteint 0, le test b = 0 est vrai : on renvoie a sans nouvel appel. La fonction s'arrête donc après un nombre fini d'appels.

Résultat : Le variant b décroît strictement (0 ⩽ a mod b < b) et reste minoré par 0 ; il atteint 0 en un nombre fini d'appels, donc pgcd termine.

Erreurs fréquentes

Affirmer « ça termine parce qu'il y a un cas de base » sans vérifier que les appels s'en rapprochent : un cas de base inatteignable ne sert à rien.
Proposer un variant qui n'est pas minoré (ex. il peut devenir négatif) ou qui ne décroît pas strictement : la justification est alors invalide.
Confondre terminaison et efficacité : fib naïf TERMINE bien (le variant n décroît), même s'il est très lent.

Révision active

On considère pgcd(a, b) défini par : si b = 0 renvoyer a, sinon renvoyer pgcd(b, a mod b). Justifier que cette fonction récursive termine en exhibant un variant entier positif strictement décroissant.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Un programme est une donnée : la calculabilité#

Vertiefungeduscol-programme-nsi-terminale

Un programme est une donnée : A reçoit P et d en arguments

Fig. 5Un programme P n'est qu'une chaîne de caractères : on peut donc le passer en ARGUMENT à un autre programme A, exactement comme une donnée. Un compilateur, un interpréteur ou un antivirus prennent du code en entrée — c'est la clé du raisonnement sur l'arrêt.

Un programme n'est rien d'autre qu'un TEXTE (une suite de caractères, un fichier). Il peut donc être stocké, transmis, et surtout passé en ARGUMENT à un autre programme : « un programme est aussi une donnée ».

C'est une réalité quotidienne de l'informatique : un compilateur, un interpréteur Python, un antivirus, un éditeur de code prennent du CODE en entrée et le traitent comme n'importe quelle donnée.

La CALCULABILITÉ étudie ce qu'un ordinateur peut, ou ne peut pas, calculer en principe — indépendamment de la vitesse ou de la mémoire de la machine. Une fonction est dite calculable s'il existe un algorithme qui la calcule pour toute entrée.

Thèse de Church-Turing (admise) : tous les modèles raisonnables de calcul (machines de Turing, fonctions récursives, langages de programmation usuels comme Python) calculent EXACTEMENT la même classe de fonctions. « Calculable » a donc un sens absolu, qui ne dépend pas du langage choisi.

Résultat fondamental : il existe des fonctions (et des problèmes) NON calculables. Tout n'est pas programmable, même avec un temps et une mémoire illimités. Le problème de l'arrêt en est l'exemple emblématique (section suivante).

Le fait que « code = donnée » est la clé technique de ces résultats : il rend possible qu'un programme RAISONNE SUR un autre programme, et même qu'un programme se prenne lui-même en entrée (auto-référence).

f \text{ est } \textbf{calculable} \iff \exists\, \text{algorithme } P,\ \forall x,\ P(x) = f(x)

Définition d'une fonction calculable

Une fonction est calculable s'il existe un algorithme qui, pour toute entrée x, s'arrête et renvoie f(x). Certaines fonctions n'ont aucun tel algorithme.

Exemple corrigé

Pourquoi « code = donnée » ? Trois exemples et leur portée

Citer trois logiciels qui prennent du code en entrée, expliquer ce qu'ils en font, et expliquer pourquoi cette idée est essentielle pour la calculabilité.

Interpréteur Python
On lui passe un fichier .py (du texte) ; il le lit comme une donnée, l'analyse, puis l'exécute. Le programme P est ici la DONNÉE d'entrée de l'interpréteur.
Compilateur
Il reçoit un code source (texte), le vérifie et le traduit en code machine. Là encore, le programme à compiler est traité comme une donnée à transformer.
Antivirus / analyseur statique
Il lit le code d'un exécutable pour décider s'il est malveillant : il RAISONNE sur un programme à partir de son texte, sans forcément l'exécuter.
Conséquence pour la calculabilité
Puisqu'un programme est un texte manipulable, on peut construire un programme A qui prend un programme P (et même P lui-même) en argument. C'est précisément ce mécanisme d'auto-référence qui permet de prouver que certains problèmes, comme l'arrêt, sont indécidables.

Résultat : Un programme est une donnée car c'est un texte que d'autres programmes (interpréteur, compilateur, antivirus) lisent et traitent. Cette propriété autorise l'auto-référence, fondement des résultats d'indécidabilité.

Erreurs fréquentes

Croire que « non calculable » signifie « trop long » ou « pas encore programmé » : un problème indécidable n'a AUCUN algorithme correct, quel que soit le temps disponible.
Penser qu'un ordinateur plus puissant (ou quantique) pourrait résoudre le problème de l'arrêt : l'indécidabilité est une limite logique, pas matérielle.
Confondre le programme (le texte) et son exécution (le processus) : c'est le texte, manipulable, qui est passé en donnée.

Révision active

Citer trois logiciels du quotidien qui prennent un programme (du code) en entrée et expliquer en une phrase, pour chacun, ce qu'ils en font. En déduire ce qu'on entend par « un programme est une donnée ».

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Décidabilité et le problème de l'arrêt#

Vertiefungeduscol-programme-nsi-terminale

Indécidabilité du problème de l'arrêt : la preuve par l'absurde

Fig. 6On suppose STOP(P, d) capable de toujours dire si P(d) s'arrête, puis on construit PARADOXE(P) : « si STOP(P, P) dit que P(P) s'arrête, alors boucler ; sinon s'arrêter ». Exécuter PARADOXE(PARADOXE) mène à une contradiction dans les deux cas : STOP ne peut donc pas exister — l'arrêt est INDÉCIDABLE (Turing, 1936).

Un PROBLÈME DE DÉCISION est une question dont la réponse est « oui » ou « non » pour chaque entrée (par exemple : « ce programme s'arrête-t-il sur cette entrée ? »). Il est DÉCIDABLE s'il existe un algorithme qui, pour TOUTE entrée, s'arrête et renvoie la bonne réponse oui/non.

Un problème est INDÉCIDABLE lorsqu'aucun algorithme de ce genre n'existe — pas même un algorithme très lent. L'indécidabilité est une impossibilité logique, démontrée, pas une simple difficulté pratique.

Le PROBLÈME DE L'ARRÊT (halting problem) : existe-t-il un algorithme STOP qui, recevant un programme P et une entrée d, répond toujours correctement « P s'arrête-t-il sur d ? » ? La réponse est NON : ce problème est indécidable (Alan Turing, 1936).

Preuve par l'absurde : on suppose STOP(P, d) existe. On construit alors PARADOXE(P) qui boucle si STOP(P, P) dit « s'arrête », et s'arrête sinon. On exécute PARADOXE(PARADOXE) : s'il s'arrête, STOP a répondu « s'arrête » donc il devait boucler ; s'il boucle, STOP a répondu « boucle » donc il devait s'arrêter. Contradiction : STOP ne peut pas exister.

Cette preuve repose entièrement sur le fait que « code = donnée » (un programme se prend lui-même en argument) : c'est l'auto-référence, dans l'esprit de l'argument diagonal de Cantor.

Portée : l'indécidabilité du problème de l'arrêt explique pourquoi aucun outil ne peut détecter automatiquement et à coup sûr TOUTES les boucles infinies d'un code quelconque. Beaucoup d'autres problèmes sont indécidables ; mais de nombreux cas particuliers restent, eux, parfaitement décidables.

\operatorname{STOP}(P, d) = \begin{cases} \text{vrai} & \text{si } P(d) \text{ s'arrête} \\ \text{faux} & \text{si } P(d) \text{ boucle} \end{cases}

L'hypothétique décideur universel d'arrêt

On SUPPOSE qu'un tel STOP existe et s'arrête toujours en donnant la bonne réponse. La preuve aboutit à une contradiction, donc STOP ne peut exister.

\operatorname{PARADOXE}(P): \quad \text{si } \operatorname{STOP}(P,P) \text{ alors boucler}\ ;\ \text{sinon s'arrêter}

Le programme auto-contradictoire

Appliqué à lui-même, PARADOXE(PARADOXE) s'arrête si et seulement s'il ne s'arrête pas : c'est la contradiction qui réfute l'existence de STOP.

Exemple corrigé

La preuve d'indécidabilité du problème de l'arrêt

Énoncer le problème de l'arrêt, puis démontrer par l'absurde qu'il est indécidable.

Énoncer le problème
Le problème de l'arrêt demande : existe-t-il un algorithme qui, recevant n'importe quel programme P et n'importe quelle entrée d, répond toujours correctement à la question « l'exécution de P sur d s'arrête-t-elle ? »
Poser l'hypothèse absurde
Supposons qu'un tel décideur STOP(P, d) existe, qu'il s'arrête toujours et renvoie « vrai » si P(d) s'arrête, « faux » sinon.
Construire le programme piège
Comme un programme est une donnée, on peut écrire PARADOXE(P) qui appelle STOP(P, P) : si la réponse est « vrai » (P(P) s'arrête), PARADOXE boucle à l'infini ; si elle est « faux », PARADOXE s'arrête aussitôt.
Appliquer PARADOXE à lui-même
Exécutons PARADOXE(PARADOXE). Premier cas : il s'arrête. Alors STOP(PARADOXE, PARADOXE) avait répondu « vrai », donc par construction PARADOXE devait BOUCLER — contradiction. Deuxième cas : il boucle. Alors STOP avait répondu « faux », donc PARADOXE devait S'ARRÊTER — contradiction encore.
Conclure
Les deux cas mènent à une contradiction. L'hypothèse de départ est donc fausse : aucun programme STOP universel n'existe. Le problème de l'arrêt est indécidable.

Résultat : Aucun algorithme ne peut décider l'arrêt de tout couple (programme, entrée) : le problème de l'arrêt est INDÉCIDABLE (Turing, 1936). C'est l'exemple canonique d'un problème indécidable.

Erreurs fréquentes

Croire qu'on peut décider l'arrêt « en exécutant le programme et en attendant » : si le programme boucle, on attendrait indéfiniment et on ne saurait jamais répondre « non » avec certitude.
Croire que l'indécidabilité concerne UN programme particulier : elle dit qu'aucun algorithme ne peut répondre pour TOUS les couples (programme, entrée). Pour un programme donné précis, on peut parfois conclure.
Oublier que c'est une preuve par l'absurde : on suppose STOP, on en tire une contradiction, donc STOP n'existe pas. Ne pas confondre avec une preuve constructive.

Révision active

Énoncer le problème de l'arrêt, puis rédiger la preuve de son indécidabilité par l'absurde : poser l'hypothèse d'un programme STOP, construire un programme auto-contradictoire, et dégager la contradiction.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en numérique et sciences informatiques — voie générale (Éduscol)

Points clés

Écrire et vérifier somme(n)

Points clés

Tracer la pile d'appels de fact(4)

Points clés

Justifier la terminaison de pgcd (algorithme d'Euclide récursif)

Points clés

Pourquoi « code = donnée » ? Trois exemples et leur portée

Points clés

La preuve d'indécidabilité du problème de l'arrêt

Sources

Récursivité, calculabilité et décidabilité

Points clés

Écrire et vérifier somme(n)

Points clés

Tracer la pile d'appels de fact(4)

Points clés

Justifier la terminaison de pgcd (algorithme d'Euclide récursif)

Points clés

Pourquoi « code = donnée » ? Trois exemples et leur portée

Points clés

La preuve d'indécidabilité du problème de l'arrêt

Sources