\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais,bloc,completemulti]{automultiplechoice}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}

\title{Récursivité}
\date{Numérique et sciences informatiques}

\begin{document}

\noindent\textbf{Récursivité} \hfill \textit{Numérique et sciences informatiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{terminalerecursivite}{
  \begin{question}{q01}
    Quelle propriété caractérise une fonction récursive ?
    \begin{choices}
    \correctchoice{Elle s'appelle elle-même, avec au moins un cas de base qui ne fait pas d'appel récursif}
    \wrongchoice{Elle prend obligatoirement deux paramètres : une valeur et une accumulation}
    \wrongchoice{Elle renvoie obligatoirement une liste qui se construit pas à pas}
    \wrongchoice{Elle utilise une boucle \texttt{while} qui décompte une variable}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q02}
    Que se passe-t-il en Python si une fonction récursive ne possède
aucun cas de base ?
    \begin{choices}
    \wrongchoice{Elle renvoie systématiquement \texttt{None}}
    \wrongchoice{Elle renvoie $0$}
    \correctchoice{Elle s'exécute infiniment et finit par lever une erreur \texttt{RecursionError}}
    \wrongchoice{Le compilateur la rejette avant exécution}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q03}
    Quand une fonction \texttt{f} s'appelle récursivement, que stocke la
pile d'appels pendant l'exécution ?
    \begin{choices}
    \wrongchoice{Une copie complète de la mémoire à chaque appel}
    \correctchoice{Le contexte de chaque appel : paramètres, variables locales et point de retour}
    \wrongchoice{Uniquement la valeur de retour de chaque appel}
    \wrongchoice{Le code source de la fonction, dupliqué à chaque appel}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q04}
    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)} ?
    \begin{choices}
    \wrongchoice{$32$}
    \correctchoice{$16$}
    \wrongchoice{$4$}
    \wrongchoice{$8$}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q05}
    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} ?
    \begin{choices}
    \wrongchoice{Elle assure que \texttt{n} reste positif pendant l'exécution}
    \wrongchoice{Elle initialise une variable de comptage}
    \correctchoice{C'est le cas de base, qui arrête la récursion sans nouvel appel}
    \wrongchoice{Elle gère uniquement les cas d'erreur quand \texttt{n} est négatif}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q06}
    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}
    \begin{choices}
    \wrongchoice{\texttt{a == 0}}
    \correctchoice{\texttt{b == 0}}
    \wrongchoice{\texttt{a == b}}
    \wrongchoice{\texttt{a \% b == 0}}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q07}
    Une fonction qui contient \textbf{deux appels récursifs} sur des
sous-problèmes différents est dite :
    \begin{choices}
    \correctchoice{Une récursivité double (ou multiple)}
    \wrongchoice{Une récursivité terminale}
    \wrongchoice{Une récursivité simple}
    \wrongchoice{Une récursivité croisée}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q08}
    Quelle propriété l'argument d'un appel récursif doit-il vérifier
pour garantir que la fonction termine ?
    \begin{choices}
    \wrongchoice{Il doit être un entier}
    \wrongchoice{Il doit augmenter strictement à chaque appel}
    \wrongchoice{Il doit rester constant tant que le cas de base n'est pas atteint}
    \correctchoice{Il doit décroître strictement à chaque appel, vers le cas de base}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q09}
    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}
    \begin{choices}
    \correctchoice{\texttt{chaine == ""}}
    \wrongchoice{\texttt{1 + compte(chaine[1:])}}
    \wrongchoice{La fonction n'a pas de cas de base}
    \wrongchoice{\texttt{chaine[1:]}}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q10}
    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) ?
    \begin{choices}
    \wrongchoice{Une suite quelconque, tirée au hasard}
    \wrongchoice{Une suite définie par $u_n = f(u_{n-1}, u_{n-2})$}
    \correctchoice{Une suite définie par $u_0$ et $u_{n} = f(u_{n-1})$}
    \wrongchoice{Une suite définie uniquement par sa valeur initiale}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q11}
    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])} ?
    \begin{choices}
    \wrongchoice{$5$}
    \wrongchoice{$30$}
    \wrongchoice{$0$}
    \correctchoice{$10$}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q12}
    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)} ?
    \begin{choices}
    \wrongchoice{$3$}
    \correctchoice{$4$}
    \wrongchoice{$10$}
    \wrongchoice{$5$}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q13}
    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}
    \begin{choices}
    \correctchoice{$0$}
    \wrongchoice{\texttt{None}}
    \wrongchoice{$1$}
    \wrongchoice{\texttt{c}}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q14}
    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}
    \begin{choices}
    \wrongchoice{\texttt{L[0] > L[-1]}}
    \wrongchoice{\texttt{L == []}}
    \wrongchoice{\texttt{len(L) == 2}}
    \correctchoice{\texttt{len(L) == 1}}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q15}
    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}
    \begin{choices}
    \correctchoice{\texttt{miroir(L[1:]) + [L[0]]}}
    \wrongchoice{\texttt{miroir(L[0]) + miroir(L[1:])}}
    \wrongchoice{\texttt{miroir(L)[1:]}}
    \wrongchoice{\texttt{[L[0]] + miroir(L[1:])}}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q16}
    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 ?
    \begin{choices}
    \wrongchoice{$100$}
    \correctchoice{$1024$}
    \wrongchoice{$20$}
    \wrongchoice{$2048$}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q17}
    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 ?
    \begin{choices}
    \wrongchoice{Aucun, c'est une fonction itérative déguisée}
    \correctchoice{Deux, un sur chaque sous-arbre}
    \wrongchoice{Autant que d'éléments dans la liste représentant l'arbre}
    \wrongchoice{Un seul, sur le sous-arbre gauche}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q18}
    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 ?
    \begin{choices}
    \correctchoice{La pile d'appels du programme a une taille limite (par défaut autour de $1000$)}
    \wrongchoice{Le cas de base met trop de temps à s'évaluer}
    \wrongchoice{La fonction utilise trop de variables locales}
    \wrongchoice{Python ne sait pas gérer la récursivité}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q19}
    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}
    \begin{choices}
    \wrongchoice{$O(n^2)$}
    \wrongchoice{$O(n)$}
    \wrongchoice{$O(\log n)$}
    \correctchoice{$O(2^n)$}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q20}
    Qu'est-ce que la \textbf{mémoïsation} d'une fonction récursive ?
    \begin{choices}
    \correctchoice{Le stockage en cache des résultats déjà calculés, pour les réutiliser sans les recalculer}
    \wrongchoice{Une technique pour réduire la profondeur de la pile d'appels}
    \wrongchoice{La conversion automatique d'une fonction récursive en boucle}
    \wrongchoice{La compression des appels récursifs en un seul}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q21}
    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 ?
    \begin{choices}
    \correctchoice{$3$}
    \wrongchoice{$2$}
    \wrongchoice{$4$}
    \wrongchoice{$7$}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q22}
    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 ?
    \begin{choices}
    \correctchoice{$T(n) = 2 \cdot T(n-1) + 1$}
    \wrongchoice{$T(n) = T(n-1) + T(n-2)$}
    \wrongchoice{$T(n) = T(n-1) + 1$}
    \wrongchoice{$T(n) = n!$}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q23}
    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 ?
    \begin{choices}
    \wrongchoice{La version récursive, plus rapide grâce à la pile d'appels}
    \wrongchoice{Aucune des deux, il faut absolument utiliser une formule fermée}
    \correctchoice{La version itérative, qui évite le débordement de pile et reste très efficace}
    \wrongchoice{Les deux versions sont strictement équivalentes en performance}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q24}
    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) ?
    \begin{choices}
    \wrongchoice{$4$}
    \correctchoice{$9$}
    \wrongchoice{$16$}
    \wrongchoice{$5$}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q25}
    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 ?
    \begin{choices}
    \wrongchoice{Le même nombre qu'avant mémoïsation}
    \wrongchoice{Exactement $1$}
    \correctchoice{Environ $20$}
    \wrongchoice{Environ $2^{20}$ (un million)}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q26}
    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 ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def f(n):
    if n <= 1:
        return n
    return f(n - 1) + f(n - 2)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def f(n):
    if n == 0:
        return None
    print(n)
    return f(n - 1) + 1
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def f(n):
    if n == 0:
        return 1
    return n * f(n - 1)
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def f(n, acc):
    if n == 0:
        return acc
    return f(n - 1, n * acc)
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q27}
    On veut transformer la fonction \texttt{factorielle} récursive
simple en une version itérative équivalente. Quel code
effectue cette conversion correctement ?
    \begin{choices}
    \wrongchoice{\begin{lstlisting}
def factorielle(n):
    if n == 0:
        return 1
    return n * factorielle(n - 1)
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def factorielle(n):
    return n ** n
\end{lstlisting}
}
    \correctchoice{\begin{lstlisting}
def factorielle(n):
    produit = 1
    for i in range(1, n + 1):
        produit = produit * i
    return produit
\end{lstlisting}
}
    \wrongchoice{\begin{lstlisting}
def factorielle(n):
    produit = 0
    for i in range(1, n + 1):
        produit = produit * i
    return produit
\end{lstlisting}
}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q28}
    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)} ?
    \begin{choices}
    \correctchoice{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}
}
    \wrongchoice{Cette construction est invalide en Python ; le
programme plante immédiatement
}
    \wrongchoice{C'est une récursivité terminale, et \texttt{pair(7)}
renvoie \texttt{True}
}
    \wrongchoice{C'est une simple récursivité double, et \texttt{pair(7)}
renvoie \texttt{True}
}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q29}
    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 ?
    \begin{choices}
    \wrongchoice{La version B utilise plus de mémoire
}
    \wrongchoice{La version A est plus rapide à l'exécution
}
    \wrongchoice{La version B donne un résultat différent
de la version A
}
    \correctchoice{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{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q30}
    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 ?
    \begin{choices}
    \correctchoice{$5$ cadres (pour \texttt{factorielle(4)}, \texttt{factorielle(3)}, \texttt{factorielle(2)}, \texttt{factorielle(1)}, \texttt{factorielle(0)})}
    \wrongchoice{$1$ cadre (Python optimise les appels récursifs)}
    \wrongchoice{$4$ cadres}
    \wrongchoice{$2$ cadres (le cadre courant et celui de la fonction qui a fait l'appel)}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q31}
    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 ?
    \begin{choices}
    \correctchoice{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)
}
    \wrongchoice{Elle a une complexité polynomiale
}
    \wrongchoice{Elle ne se calcule jamais (récursion
infinie)
}
    \wrongchoice{Elle calcule simplement la somme $m + n$
}
    \end{choices}
  \end{question}
}

\element{terminalerecursivite}{
  \begin{question}{q32}
    Pour calculer $\mathrm{fib}(50)$, le temps
d'exécution sur un PC moderne est :
    \begin{choices}
    \wrongchoice{Les deux versions sont instantanées
}
    \wrongchoice{Les deux versions plantent par
dépassement de pile
}
    \correctchoice{Quelques millisecondes pour la version
itérative ; plusieurs dizaines de
minutes, voire plus, pour la version
récursive naïve
}
    \wrongchoice{Les deux versions sont équivalentes en
temps
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{terminalerecursivite}
  \insertgroup{terminalerecursivite}
}

\end{document}
