\documentclass[10pt,aspectratio=169]{beamer}

% --- Thème ---
\usetheme[language=french]{Celestia}

% Avec [allowframebreaks] sur les frames de questions, Beamer ajoute
% par défaut « (1) », « (2) », « (3) »... sur chaque sous-slide. On
% supprime entièrement cette annotation : un template vide pour
% « frametitle continuation ». L'enseignant identifie visuellement la
% continuation par le contenu de la slide. (Les variantes [from second]
% et [roman] interagissent mal avec un titre contenant \textemdash{}
% sous Celestia : elles déclenchent une erreur « Missing $ inserted ».)
\setbeamertemplate{frametitle continuation}{}

\subject{Numérique et sciences informatiques}
\title{Récursivité}
\subtitle{QCM}
\author{Terminale}
\date{\today}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

% Q1 - Réponse en A
\begin{frame}[fragile]{Question 1 \textemdash{} Définition d'une fonction récursive}
    Quelle propriété caractérise une fonction récursive ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Elle s'appelle elle-même, avec au moins un cas de base qui ne fait pas d'appel récursif}
        \item[B.] Elle prend obligatoirement deux paramètres : une valeur et une accumulation
        \item[C.] Elle renvoie obligatoirement une liste qui se construit pas à pas
        \item[D.] Elle utilise une boucle \texttt{while} qui décompte une variable
    \end{itemize}
\end{frame}

% Q2 - Réponse en C
\begin{frame}[fragile]{Question 2 \textemdash{} Nécessité du cas de base}
    Que se passe-t-il en Python si une fonction récursive ne possède
aucun cas de base ?\medskip
    \begin{itemize}
        \item[A.] Elle renvoie systématiquement \texttt{None}
        \item[B.] Elle renvoie $0$
        \item[\alert<2>{C.}] \alert<2>{Elle s'exécute infiniment et finit par lever une erreur \texttt{RecursionError}}
        \item[D.] Le compilateur la rejette avant exécution
    \end{itemize}
\end{frame}

% Q3 - Réponse en B
\begin{frame}[fragile]{Question 3 \textemdash{} Rôle de la pile d'appels}
    Quand une fonction \texttt{f} s'appelle récursivement, que stocke la
pile d'appels pendant l'exécution ?\medskip
    \begin{itemize}
        \item[A.] Une copie complète de la mémoire à chaque appel
        \item[\alert<2>{B.}] \alert<2>{Le contexte de chaque appel : paramètres, variables locales et point de retour}
        \item[C.] Uniquement la valeur de retour de chaque appel
        \item[D.] Le code source de la fonction, dupliqué à chaque appel
    \end{itemize}
\end{frame}

% Q4 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 4 \textemdash{} Évaluation d'une récurrence simple}
    On considère la fonction Python suivante :

\begin{lstlisting}
def f(n):
    if n == 0:
        return 1
    return 2 * f(n - 1)
\end{lstlisting}

Que renvoie l'appel \texttt{f(4)} ?\medskip
    \begin{itemize}
        \item[A.] $32$
        \item[B.] $16$
        \item[C.] $4$
        \item[D.] $8$
    \end{itemize}
\end{frame}

% Q4 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 4 \textemdash{} Évaluation d'une récurrence simple}
    On considère la fonction Python suivante :

\begin{lstlisting}
def f(n):
    if n == 0:
        return 1
    return 2 * f(n - 1)
\end{lstlisting}

Que renvoie l'appel \texttt{f(4)} ?\medskip
    \begin{itemize}
        \item[A.] $32$
        \item[\alert{B.}] \alert{$16$}
        \item[C.] $4$
        \item[D.] $8$
    \end{itemize}
\end{frame}

% Q5 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 5 \textemdash{} Identifier le cas de base de la factorielle}
    On définit \texttt{factorielle} ainsi :

\begin{lstlisting}
def factorielle(n):
    if n <= 1:
        return 1
    return n * factorielle(n - 1)
\end{lstlisting}

Quel est le rôle de la condition \texttt{if n <= 1: return 1} ?\medskip
    \begin{itemize}
        \item[A.] Elle assure que \texttt{n} reste positif pendant l'exécution
        \item[B.] Elle initialise une variable de comptage
        \item[C.] C'est le cas de base, qui arrête la récursion sans nouvel appel
        \item[D.] Elle gère uniquement les cas d'erreur quand \texttt{n} est négatif
    \end{itemize}
\end{frame}

% Q5 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 5 \textemdash{} Identifier le cas de base de la factorielle}
    On définit \texttt{factorielle} ainsi :

\begin{lstlisting}
def factorielle(n):
    if n <= 1:
        return 1
    return n * factorielle(n - 1)
\end{lstlisting}

Quel est le rôle de la condition \texttt{if n <= 1: return 1} ?\medskip
    \begin{itemize}
        \item[A.] Elle assure que \texttt{n} reste positif pendant l'exécution
        \item[B.] Elle initialise une variable de comptage
        \item[\alert{C.}] \alert{C'est le cas de base, qui arrête la récursion sans nouvel appel}
        \item[D.] Elle gère uniquement les cas d'erreur quand \texttt{n} est négatif
    \end{itemize}
\end{frame}

% Q6 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 6 \textemdash{} Identifier le cas de base de l'algorithme d'Euclide}
    Dans la fonction suivante, qui calcule le PGCD de deux entiers,
quel est le cas de base ?

\begin{lstlisting}
def pgcd(a, b):
    if b == 0:
        return a
    return pgcd(b, a % b)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] \texttt{a == 0}
        \item[B.] \texttt{b == 0}
        \item[C.] \texttt{a == b}
        \item[D.] \texttt{a \% b == 0}
    \end{itemize}
\end{frame}

% Q6 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 6 \textemdash{} Identifier le cas de base de l'algorithme d'Euclide}
    Dans la fonction suivante, qui calcule le PGCD de deux entiers,
quel est le cas de base ?

\begin{lstlisting}
def pgcd(a, b):
    if b == 0:
        return a
    return pgcd(b, a % b)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] \texttt{a == 0}
        \item[\alert{B.}] \alert{\texttt{b == 0}}
        \item[C.] \texttt{a == b}
        \item[D.] \texttt{a \% b == 0}
    \end{itemize}
\end{frame}

% Q7 - Réponse en A
\begin{frame}[fragile]{Question 7 \textemdash{} Récursivité simple ou récursivité double}
    Une fonction qui contient \textbf{deux appels récursifs} sur des
sous-problèmes différents est dite :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Une récursivité double (ou multiple)}
        \item[B.] Une récursivité terminale
        \item[C.] Une récursivité simple
        \item[D.] Une récursivité croisée
    \end{itemize}
\end{frame}

% Q8 - Réponse en D
\begin{frame}[fragile]{Question 8 \textemdash{} Garantir la terminaison}
    Quelle propriété l'argument d'un appel récursif doit-il vérifier
pour garantir que la fonction termine ?\medskip
    \begin{itemize}
        \item[A.] Il doit être un entier
        \item[B.] Il doit augmenter strictement à chaque appel
        \item[C.] Il doit rester constant tant que le cas de base n'est pas atteint
        \item[\alert<2>{D.}] \alert<2>{Il doit décroître strictement à chaque appel, vers le cas de base}
    \end{itemize}
\end{frame}

% Q9 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 9 \textemdash{} Lecture d'une récursion sur les chaînes}
    Dans la fonction suivante, quel est le cas de base ?

\begin{lstlisting}
def compte(chaine):
    if chaine == "":
        return 0
    return 1 + compte(chaine[1:])
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] \texttt{chaine == ""}
        \item[B.] \texttt{1 + compte(chaine[1:])}
        \item[C.] La fonction n'a pas de cas de base
        \item[D.] \texttt{chaine[1:]}
    \end{itemize}
\end{frame}

% Q9 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 9 \textemdash{} Lecture d'une récursion sur les chaînes}
    Dans la fonction suivante, quel est le cas de base ?

\begin{lstlisting}
def compte(chaine):
    if chaine == "":
        return 0
    return 1 + compte(chaine[1:])
\end{lstlisting}\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{\texttt{chaine == ""}}
        \item[B.] \texttt{1 + compte(chaine[1:])}
        \item[C.] La fonction n'a pas de cas de base
        \item[D.] \texttt{chaine[1:]}
    \end{itemize}
\end{frame}

% Q10 - Réponse en C
\begin{frame}[fragile]{Question 10 \textemdash{} Récursivité et définition par récurrence}
    Quelle suite mathématique peut être implémentée le plus
naturellement par une fonction récursive simple (un seul appel
récursif par cas) ?\medskip
    \begin{itemize}
        \item[A.] Une suite quelconque, tirée au hasard
        \item[B.] Une suite définie par $u_n = f(u_{n-1}, u_{n-2})$
        \item[\alert<2>{C.}] \alert<2>{Une suite définie par $u_0$ et $u_{n} = f(u_{n-1})$}
        \item[D.] Une suite définie uniquement par sa valeur initiale
    \end{itemize}
\end{frame}

% Q11 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 11 \textemdash{} Déroulement d'une somme récursive}
    On considère :

\begin{lstlisting}
def somme(L):
    if L == []:
        return 0
    return L[0] + somme(L[1:])
\end{lstlisting}

Que renvoie \texttt{somme([3, 5, 2])} ?\medskip
    \begin{itemize}
        \item[A.] $5$
        \item[B.] $30$
        \item[C.] $0$
        \item[D.] $10$
    \end{itemize}
\end{frame}

% Q11 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 11 \textemdash{} Déroulement d'une somme récursive}
    On considère :

\begin{lstlisting}
def somme(L):
    if L == []:
        return 0
    return L[0] + somme(L[1:])
\end{lstlisting}

Que renvoie \texttt{somme([3, 5, 2])} ?\medskip
    \begin{itemize}
        \item[A.] $5$
        \item[B.] $30$
        \item[C.] $0$
        \item[\alert{D.}] \alert{$10$}
    \end{itemize}
\end{frame}

% Q12 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 12 \textemdash{} Compter les chiffres d'un entier}
    On considère :

\begin{lstlisting}
def nb_chiffres(n):
    if n < 10:
        return 1
    return 1 + nb_chiffres(n // 10)
\end{lstlisting}

Que renvoie \texttt{nb\_chiffres(4073)} ?\medskip
    \begin{itemize}
        \item[A.] $3$
        \item[B.] $4$
        \item[C.] $10$
        \item[D.] $5$
    \end{itemize}
\end{frame}

% Q12 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 12 \textemdash{} Compter les chiffres d'un entier}
    On considère :

\begin{lstlisting}
def nb_chiffres(n):
    if n < 10:
        return 1
    return 1 + nb_chiffres(n // 10)
\end{lstlisting}

Que renvoie \texttt{nb\_chiffres(4073)} ?\medskip
    \begin{itemize}
        \item[A.] $3$
        \item[\alert{B.}] \alert{$4$}
        \item[C.] $10$
        \item[D.] $5$
    \end{itemize}
\end{frame}

% Q13 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 13 \textemdash{} Compléter une fonction récursive}
    Pour que la fonction suivante renvoie le nombre d'occurrences
d'un caractère \texttt{c} dans une chaîne \texttt{s}, par quoi faut-il
remplacer les pointillés ?

\begin{lstlisting}
def occurrences(s, c):
    if s == "":
        return ...
    if s[0] == c:
        return 1 + occurrences(s[1:], c)
    return occurrences(s[1:], c)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] $0$
        \item[B.] \texttt{None}
        \item[C.] $1$
        \item[D.] \texttt{c}
    \end{itemize}
\end{frame}

% Q13 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 13 \textemdash{} Compléter une fonction récursive}
    Pour que la fonction suivante renvoie le nombre d'occurrences
d'un caractère \texttt{c} dans une chaîne \texttt{s}, par quoi faut-il
remplacer les pointillés ?

\begin{lstlisting}
def occurrences(s, c):
    if s == "":
        return ...
    if s[0] == c:
        return 1 + occurrences(s[1:], c)
    return occurrences(s[1:], c)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{$0$}
        \item[B.] \texttt{None}
        \item[C.] $1$
        \item[D.] \texttt{c}
    \end{itemize}
\end{frame}

% Q14 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 14 \textemdash{} Maximum d'une liste sans \texttt{max}}
    On souhaite écrire récursivement le maximum d'une liste non vide.
Quel est le \textbf{cas de base} approprié ?

\begin{lstlisting}
def maximum(L):
    if ...:
        return L[0]
    ...
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] \texttt{L[0] > L[-1]}
        \item[B.] \texttt{L == []}
        \item[C.] \texttt{len(L) == 2}
        \item[D.] \texttt{len(L) == 1}
    \end{itemize}
\end{frame}

% Q14 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 14 \textemdash{} Maximum d'une liste sans \texttt{max}}
    On souhaite écrire récursivement le maximum d'une liste non vide.
Quel est le \textbf{cas de base} approprié ?

\begin{lstlisting}
def maximum(L):
    if ...:
        return L[0]
    ...
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] \texttt{L[0] > L[-1]}
        \item[B.] \texttt{L == []}
        \item[C.] \texttt{len(L) == 2}
        \item[\alert{D.}] \alert{\texttt{len(L) == 1}}
    \end{itemize}
\end{frame}

% Q15 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 15 \textemdash{} Inversion récursive d'une liste}
    Quelle expression complète correctement la fonction \texttt{miroir}
ci-dessous, qui doit renvoyer la liste inversée ?

\begin{lstlisting}
def miroir(L):
    if L == []:
        return []
    return ...
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] \texttt{miroir(L[1:]) + [L[0]]}
        \item[B.] \texttt{miroir(L[0]) + miroir(L[1:])}
        \item[C.] \texttt{miroir(L)[1:]}
        \item[D.] \texttt{[L[0]] + miroir(L[1:])}
    \end{itemize}
\end{frame}

% Q15 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 15 \textemdash{} Inversion récursive d'une liste}
    Quelle expression complète correctement la fonction \texttt{miroir}
ci-dessous, qui doit renvoyer la liste inversée ?

\begin{lstlisting}
def miroir(L):
    if L == []:
        return []
    return ...
\end{lstlisting}\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{\texttt{miroir(L[1:]) + [L[0]]}}
        \item[B.] \texttt{miroir(L[0]) + miroir(L[1:])}
        \item[C.] \texttt{miroir(L)[1:]}
        \item[D.] \texttt{[L[0]] + miroir(L[1:])}
    \end{itemize}
\end{frame}

% Q16 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 16 \textemdash{} Croissance d'une population}
    Un biologiste modélise une population de bactéries qui double
chaque heure, en partant d'une seule bactérie. Si la fonction
récursive est :

\begin{lstlisting}
def population(n):
    if n == 0:
        return 1
    return 2 * population(n - 1)
\end{lstlisting}

Combien de bactéries y a-t-il après $10$ heures ?\medskip
    \begin{itemize}
        \item[A.] $100$
        \item[B.] $1024$
        \item[C.] $20$
        \item[D.] $2048$
    \end{itemize}
\end{frame}

% Q16 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 16 \textemdash{} Croissance d'une population}
    Un biologiste modélise une population de bactéries qui double
chaque heure, en partant d'une seule bactérie. Si la fonction
récursive est :

\begin{lstlisting}
def population(n):
    if n == 0:
        return 1
    return 2 * population(n - 1)
\end{lstlisting}

Combien de bactéries y a-t-il après $10$ heures ?\medskip
    \begin{itemize}
        \item[A.] $100$
        \item[\alert{B.}] \alert{$1024$}
        \item[C.] $20$
        \item[D.] $2048$
    \end{itemize}
\end{frame}

% Q17 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 17 \textemdash{} Récursivité sur un arbre binaire}
    On parcourt un arbre binaire avec la fonction :

\begin{lstlisting}
def cherche(elt, arbre):
    if arbre is None:
        return False
    if arbre.valeur == elt:
        return True
    return cherche(elt, arbre.gauche) or cherche(elt, arbre.droite)
\end{lstlisting}

Combien d'appels récursifs cette fonction génère-t-elle au
maximum dans une seule exécution ?\medskip
    \begin{itemize}
        \item[A.] Aucun, c'est une fonction itérative déguisée
        \item[B.] Deux, un sur chaque sous-arbre
        \item[C.] Autant que d'éléments dans la liste représentant l'arbre
        \item[D.] Un seul, sur le sous-arbre gauche
    \end{itemize}
\end{frame}

% Q17 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 17 \textemdash{} Récursivité sur un arbre binaire}
    On parcourt un arbre binaire avec la fonction :

\begin{lstlisting}
def cherche(elt, arbre):
    if arbre is None:
        return False
    if arbre.valeur == elt:
        return True
    return cherche(elt, arbre.gauche) or cherche(elt, arbre.droite)
\end{lstlisting}

Combien d'appels récursifs cette fonction génère-t-elle au
maximum dans une seule exécution ?\medskip
    \begin{itemize}
        \item[A.] Aucun, c'est une fonction itérative déguisée
        \item[\alert{B.}] \alert{Deux, un sur chaque sous-arbre}
        \item[C.] Autant que d'éléments dans la liste représentant l'arbre
        \item[D.] Un seul, sur le sous-arbre gauche
    \end{itemize}
\end{frame}

% Q18 - Réponse en A
\begin{frame}[fragile]{Question 18 \textemdash{} Limite pratique de la récursion en Python}
    Pour quelle raison principale Python lève-t-il une
\texttt{RecursionError} lors d'une récursion trop profonde, même si la
fonction comporte un cas de base correct ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{La pile d'appels du programme a une taille limite (par défaut autour de $1000$)}
        \item[B.] Le cas de base met trop de temps à s'évaluer
        \item[C.] La fonction utilise trop de variables locales
        \item[D.] Python ne sait pas gérer la récursivité
    \end{itemize}
\end{frame}

% Q19 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 19 \textemdash{} Complexité de Fibonacci récursif naïf}
    Quelle est la complexité en temps de la fonction suivante,
appelée pour calculer \texttt{fibonacci(n)} ?

\begin{lstlisting}
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] $O(n^2)$
        \item[B.] $O(n)$
        \item[C.] $O(\log n)$
        \item[D.] $O(2^n)$
    \end{itemize}
\end{frame}

% Q19 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 19 \textemdash{} Complexité de Fibonacci récursif naïf}
    Quelle est la complexité en temps de la fonction suivante,
appelée pour calculer \texttt{fibonacci(n)} ?

\begin{lstlisting}
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] $O(n^2)$
        \item[B.] $O(n)$
        \item[C.] $O(\log n)$
        \item[\alert{D.}] \alert{$O(2^n)$}
    \end{itemize}
\end{frame}

% Q20 - Réponse en A
\begin{frame}[fragile]{Question 20 \textemdash{} Principe de la mémoïsation}
    Qu'est-ce que la \textbf{mémoïsation} d'une fonction récursive ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Le stockage en cache des résultats déjà calculés, pour les réutiliser sans les recalculer}
        \item[B.] Une technique pour réduire la profondeur de la pile d'appels
        \item[C.] La conversion automatique d'une fonction récursive en boucle
        \item[D.] La compression des appels récursifs en un seul
    \end{itemize}
\end{frame}

% Q21 - Réponse en A
\begin{frame}[fragile]{Question 21 \textemdash{} Tours de Hanoï avec deux disques}
    Pour résoudre le problème des tours de Hanoï avec $2$ disques
(déplacer la pile de A vers C en utilisant B), combien de
déplacements minimum sont nécessaires ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$3$}
        \item[B.] $2$
        \item[C.] $4$
        \item[D.] $7$
    \end{itemize}
\end{frame}

% Q22 - Réponse en A
\begin{frame}[fragile]{Question 22 \textemdash{} Récurrence des tours de Hanoï}
    Quelle relation de récurrence vérifie $T(n)$, le nombre de
déplacements minimum pour résoudre les tours de Hanoï avec $n$
disques ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$T(n) = 2 \cdot T(n-1) + 1$}
        \item[B.] $T(n) = T(n-1) + T(n-2)$
        \item[C.] $T(n) = T(n-1) + 1$
        \item[D.] $T(n) = n!$
    \end{itemize}
\end{frame}

% Q23 - Réponse en C
\begin{frame}[fragile]{Question 23 \textemdash{} Choisir entre récursif et itératif}
    Pour calculer la somme des $n$ premiers entiers, on peut écrire
une boucle ou une fonction récursive. Pour $n = 10\ 000$ en
Python, quelle version est préférable ?\medskip
    \begin{itemize}
        \item[A.] La version récursive, plus rapide grâce à la pile d'appels
        \item[B.] Aucune des deux, il faut absolument utiliser une formule fermée
        \item[\alert<2>{C.}] \alert<2>{La version itérative, qui évite le débordement de pile et reste très efficace}
        \item[D.] Les deux versions sont strictement équivalentes en performance
    \end{itemize}
\end{frame}

% Q24 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 24 \textemdash{} Analyse d'une récursion mystère}
    On considère :

\begin{lstlisting}
def f(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return f(n - 1) + f(n - 2) + 1
\end{lstlisting}

Combien d'\textbf{appels récursifs au total} sont effectués pour
calculer \texttt{f(4)} (en comptant l'appel initial) ?\medskip
    \begin{itemize}
        \item[A.] $4$
        \item[B.] $9$
        \item[C.] $16$
        \item[D.] $5$
    \end{itemize}
\end{frame}

% Q24 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 24 \textemdash{} Analyse d'une récursion mystère}
    On considère :

\begin{lstlisting}
def f(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return f(n - 1) + f(n - 2) + 1
\end{lstlisting}

Combien d'\textbf{appels récursifs au total} sont effectués pour
calculer \texttt{f(4)} (en comptant l'appel initial) ?\medskip
    \begin{itemize}
        \item[A.] $4$
        \item[\alert{B.}] \alert{$9$}
        \item[C.] $16$
        \item[D.] $5$
    \end{itemize}
\end{frame}

% Q25 - Réponse en C
\begin{frame}[fragile]{Question 25 \textemdash{} Effet de la mémoïsation}
    On mémoïse la fonction Fibonacci avec un dictionnaire de cache.
Combien d'appels effectifs (calculs réels, avant cache) sont
effectués pour \texttt{fibonacci(20)} après mémoïsation ?\medskip
    \begin{itemize}
        \item[A.] Le même nombre qu'avant mémoïsation
        \item[B.] Exactement $1$
        \item[\alert<2>{C.}] \alert<2>{Environ $20$}
        \item[D.] Environ $2^{20}$ (un million)
    \end{itemize}
\end{frame}

% Q26 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Récursivité terminale}
    Une fonction récursive est dite \textbf{terminale} quand son
appel récursif est la \textbf{dernière opération} effectuée
dans la fonction. Parmi les fonctions suivantes,
laquelle est récursive terminale ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def f(n):
    if n <= 1:
        return n
    return f(n - 1) + f(n - 2)
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def f(n):
    if n == 0:
        return None
    print(n)
    return f(n - 1) + 1
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def f(n):
    if n == 0:
        return 1
    return n * f(n - 1)
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def f(n, acc):
    if n == 0:
        return acc
    return f(n - 1, n * acc)
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q26 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Récursivité terminale}
    Une fonction récursive est dite \textbf{terminale} quand son
appel récursif est la \textbf{dernière opération} effectuée
dans la fonction. Parmi les fonctions suivantes,
laquelle est récursive terminale ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def f(n):
    if n <= 1:
        return n
    return f(n - 1) + f(n - 2)
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def f(n):
    if n == 0:
        return None
    print(n)
    return f(n - 1) + 1
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def f(n):
    if n == 0:
        return 1
    return n * f(n - 1)
\end{lstlisting}

        \item[\alert{D.}]~\\
\begin{lstlisting}
def f(n, acc):
    if n == 0:
        return acc
    return f(n - 1, n * acc)
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q27 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 27 \textemdash{} Convertir une récursion en itération}
    On veut transformer la fonction \texttt{factorielle} récursive
simple en une version itérative équivalente. Quel code
effectue cette conversion correctement ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def factorielle(n):
    if n == 0:
        return 1
    return n * factorielle(n - 1)
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def factorielle(n):
    return n ** n
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
def factorielle(n):
    produit = 1
    for i in range(1, n + 1):
        produit = produit * i
    return produit
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def factorielle(n):
    produit = 0
    for i in range(1, n + 1):
        produit = produit * i
    return produit
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q27 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 27 \textemdash{} Convertir une récursion en itération}
    On veut transformer la fonction \texttt{factorielle} récursive
simple en une version itérative équivalente. Quel code
effectue cette conversion correctement ?\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
def factorielle(n):
    if n == 0:
        return 1
    return n * factorielle(n - 1)
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
def factorielle(n):
    return n ** n
\end{lstlisting}

        \item[\alert{C.}]~\\
\begin{lstlisting}
def factorielle(n):
    produit = 1
    for i in range(1, n + 1):
        produit = produit * i
    return produit
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
def factorielle(n):
    produit = 0
    for i in range(1, n + 1):
        produit = produit * i
    return produit
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q28 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 28 \textemdash{} Récursivité croisée}
    On définit deux fonctions qui s'appellent mutuellement :
\begin{lstlisting}
def pair(n):
    if n == 0:
        return True
    return impair(n - 1)

def impair(n):
    if n == 0:
        return False
    return pair(n - 1)
\end{lstlisting}
Comment qualifier cette construction et que renvoie
\texttt{pair(7)} ?\medskip
    \begin{itemize}
        \item[A.] C'est de la récursivité croisée (ou mutuelle) :
deux fonctions s'appellent l'une l'autre, formant
ensemble un schéma récursif. \texttt{pair(7)} renvoie \texttt{False}

        \item[B.] Cette construction est invalide en Python ; le
programme plante immédiatement

        \item[C.] C'est une récursivité terminale, et \texttt{pair(7)}
renvoie \texttt{True}

        \item[D.] C'est une simple récursivité double, et \texttt{pair(7)}
renvoie \texttt{True}

    \end{itemize}
\end{frame}

% Q28 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 28 \textemdash{} Récursivité croisée}
    On définit deux fonctions qui s'appellent mutuellement :
\begin{lstlisting}
def pair(n):
    if n == 0:
        return True
    return impair(n - 1)

def impair(n):
    if n == 0:
        return False
    return pair(n - 1)
\end{lstlisting}
Comment qualifier cette construction et que renvoie
\texttt{pair(7)} ?\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{C'est de la récursivité croisée (ou mutuelle) :
deux fonctions s'appellent l'une l'autre, formant
ensemble un schéma récursif. \texttt{pair(7)} renvoie \texttt{False}
}
        \item[B.] Cette construction est invalide en Python ; le
programme plante immédiatement

        \item[C.] C'est une récursivité terminale, et \texttt{pair(7)}
renvoie \texttt{True}

        \item[D.] C'est une simple récursivité double, et \texttt{pair(7)}
renvoie \texttt{True}

    \end{itemize}
\end{frame}

% Q29 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 29 \textemdash{} Récursivité avec accumulateur}
    Voici deux écritures de la fonction qui calcule
la somme des entiers de $1$ à $n$ :

\begin{lstlisting}
# Version A
def somme_a(n):
    if n == 0:
        return 0
    return n + somme_a(n - 1)

# Version B
def somme_b(n, acc=0):
    if n == 0:
        return acc
    return somme_b(n - 1, acc + n)
\end{lstlisting}

Quelle est la \textbf{différence essentielle} entre
les deux versions ?\medskip
    \begin{itemize}
        \item[A.] La version B utilise plus de mémoire

        \item[B.] La version A est plus rapide à l'exécution

        \item[C.] La version B donne un résultat différent
de la version A

        \item[D.] La version A laisse une opération en
attente après chaque appel récursif (le
\texttt{n + ...}), tandis que la version B passe
le résultat partiel par un accumulateur
et n'a aucune opération en attente. La
version B est dite récursive terminale

    \end{itemize}
\end{frame}

% Q29 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 29 \textemdash{} Récursivité avec accumulateur}
    Voici deux écritures de la fonction qui calcule
la somme des entiers de $1$ à $n$ :

\begin{lstlisting}
# Version A
def somme_a(n):
    if n == 0:
        return 0
    return n + somme_a(n - 1)

# Version B
def somme_b(n, acc=0):
    if n == 0:
        return acc
    return somme_b(n - 1, acc + n)
\end{lstlisting}

Quelle est la \textbf{différence essentielle} entre
les deux versions ?\medskip
    \begin{itemize}
        \item[A.] La version B utilise plus de mémoire

        \item[B.] La version A est plus rapide à l'exécution

        \item[C.] La version B donne un résultat différent
de la version A

        \item[\alert{D.}] \alert{La version A laisse une opération en
attente après chaque appel récursif (le
\texttt{n + ...}), tandis que la version B passe
le résultat partiel par un accumulateur
et n'a aucune opération en attente. La
version B est dite récursive terminale
}
    \end{itemize}
\end{frame}

% Q30 - Réponse en A
\begin{frame}[fragile]{Question 30 \textemdash{} Trace de la pile d'appels}
    Lors de l'appel \texttt{factorielle(4)} (avec la
définition récursive standard), combien de
cadres d'exécution sont \textbf{simultanément}
empilés au moment où le cas de base est
atteint ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$5$ cadres (pour \texttt{factorielle(4)}, \texttt{factorielle(3)}, \texttt{factorielle(2)}, \texttt{factorielle(1)}, \texttt{factorielle(0)})}
        \item[B.] $1$ cadre (Python optimise les appels récursifs)
        \item[C.] $4$ cadres
        \item[D.] $2$ cadres (le cadre courant et celui de la fonction qui a fait l'appel)
    \end{itemize}
\end{frame}

% Q31 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 31 \textemdash{} Fonction d'Ackermann}
    La fonction d'Ackermann est définie par :
\begin{lstlisting}
A(0, n) = n + 1
A(m, 0) = A(m - 1, 1) si m > 0
A(m, n) = A(m - 1, A(m, n - 1)) si m > 0 et n > 0
\end{lstlisting}
Quelle est sa caractéristique remarquable ?\medskip
    \begin{itemize}
        \item[A.] Elle croît extrêmement vite : par exemple
$A(4, 2)$ est un nombre comportant des
milliers de chiffres. Elle est calculable
mais n'est pas primitive récursive,
c'est-à-dire qu'elle ne peut pas être
obtenue par les schémas de récurrence
simples (sans appels imbriqués)

        \item[B.] Elle a une complexité polynomiale

        \item[C.] Elle ne se calcule jamais (récursion
infinie)

        \item[D.] Elle calcule simplement la somme $m + n$

    \end{itemize}
\end{frame}

% Q31 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 31 \textemdash{} Fonction d'Ackermann}
    La fonction d'Ackermann est définie par :
\begin{lstlisting}
A(0, n) = n + 1
A(m, 0) = A(m - 1, 1) si m > 0
A(m, n) = A(m - 1, A(m, n - 1)) si m > 0 et n > 0
\end{lstlisting}
Quelle est sa caractéristique remarquable ?\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{Elle croît extrêmement vite : par exemple
$A(4, 2)$ est un nombre comportant des
milliers de chiffres. Elle est calculable
mais n'est pas primitive récursive,
c'est-à-dire qu'elle ne peut pas être
obtenue par les schémas de récurrence
simples (sans appels imbriqués)
}
        \item[B.] Elle a une complexité polynomiale

        \item[C.] Elle ne se calcule jamais (récursion
infinie)

        \item[D.] Elle calcule simplement la somme $m + n$

    \end{itemize}
\end{frame}

% Q32 - Réponse en C
\begin{frame}[fragile]{Question 32 \textemdash{} Fibonacci itératif vs récursif}
    Pour calculer $\mathrm{fib}(50)$, le temps
d'exécution sur un PC moderne est :\medskip
    \begin{itemize}
        \item[A.] Les deux versions sont instantanées

        \item[B.] Les deux versions plantent par
dépassement de pile

        \item[\alert<2>{C.}] \alert<2>{Quelques millisecondes pour la version
itérative ; plusieurs dizaines de
minutes, voire plus, pour la version
récursive naïve
}
        \item[D.] Les deux versions sont équivalentes en
temps

    \end{itemize}
\end{frame}

\begin{frame}[standout]{}
    Fin de l'évaluation
\end{frame}

\end{document}
