Fonction récursive inconnue : type de retour, condition d’arrêt, trace des appels, rôle, version itérative

1. Idée : regarder les trois instructions Retourner. Le cas d’arrêt retourne ch, une chaîne ; la deuxième branche retourne directement le résultat d’un appel de Quoi, la troisième concatène le caractère ch[0] à ce résultat : le résultat est de type $\boxed{\text{Chaîne de caractères}}$, même lorsqu’il ne contient qu’un caractère.

Fonction Quoi (ch : Chaîne) : Chaîne

2. La condition d’arrêt est le test Long(ch) ≤ 1 : une chaîne vide ou d’un seul caractère est retournée telle quelle. Quoi("") retourne "" dès l’appel initial. Pour "aaaa", chaque caractère égal à son voisin est effacé sans être gardé : "aaaa" → "aaa" → "aa" → "a", et l’on retourne "a".

3. Idée : chaque appel efface un seul caractère, donc la longueur diminue de 1 ; le caractère gardé n’est ajouté qu’au retour de l’appel suivant.

On retourne "Apele", après 7 appels : un par caractère de "Appelle".

4. La fonction Quoi retourne la chaîne ch dans laquelle chaque groupe de caractères identiques consécutifs est réduit à un seul caractère ; Quoi("Mississippi") retourne "Misisipi". La comparaison distingue majuscules et minuscules : Quoi("Aa") retourne "Aa".

5. Idée : même parcours et même condition d’arrêt que Quoi ; on remplace la concaténation par un comptage.

Fonction NbDoubles (ch : Chaîne) : Entier
DEBUT
  Si Long(ch) ≤ 1 Alors
    Retourner 0
  Sinon
    s ← Effacer(ch, 0, 1)
    Si ch[0] = ch[1] Alors
      Retourner 1 + NbDoubles(s)
    Sinon
      Retourner NbDoubles(s)
    FinSi
  FinSi
FIN

Objet local : s, de type Chaîne, ch privée de son caractère de rang 0. "Appelle" contient les doublons pp et ll (2) ; "Mississippi" contient ss, ss et pp (3). On vérifie que la longueur de Quoi(ch) vaut Long(ch) − NbDoubles(ch) : 7 − 2 = 5 caractères pour "Apele", 11 − 3 = 8 pour "Misisipi".

1. b) Réel — la fonction retourne b − a, différence de deux paramètres réels : le résultat est un Réel. Il n’y a ni Vrai ni Faux (pas Booléen), et un Entier ne pourrait pas contenir le résultat 2,5 obtenu pour a = 4,5 et b = 2.

2. b) a ≤ b — c’est le test qui met fin aux appels. Retourner b - a est le traitement exécuté quand il est vrai ; Retourner Quoi(b, a) est l’appel récursif.

3. c) 9 — Quoi(13, 4) : 13 ≤ 4 est faux, appel Quoi(4, 13) ; 4 ≤ 13 est vrai, on retourne 13 − 4 = $\boxed{9}$.

4. a) au plus 2 — Idée : ici ce n’est pas une taille qui décroît, c’est l’ordre des arguments que l’appel rétablit. Si a ≤ b, un seul appel. Sinon b < a, et l’appel Quoi(b, a) reçoit un premier argument inférieur au second : son test est vrai, il s’arrête. Deux appels au maximum, quelle que soit la distance entre a et b.

5. b) — si a ≤ b, on retourne b − a ≥ 0 ; sinon l’appel retourne a − b > 0. Dans les deux cas, c’est la distance |a − b| : Quoi(13, 4) et Quoi(4, 13) retournent 9 tous les deux. La réponse c) serait juste si la branche d’arrêt retournait b au lieu de b − a.

1. La fonction retourne k ou n, deux entiers : Fonction Quoi (n, k : Entier) : Entier. Le type n’est pas Booléen : c’est la fonction de la question 5 qui répondra par Vrai ou Faux.

2. Idée : à chaque appel, tester d’abord n Mod k, puis k × k > n ; sinon recommencer avec k + 1.

Détail pour 35 : 35 Mod 2 = 1 et 4 ≤ 35, puis 35 Mod 3 = 2 et 9 ≤ 35, puis 35 Mod 4 = 3 et 16 ≤ 35, enfin 35 Mod 5 = 0 : on retourne $\boxed{5}$. Pour 29, les restes par 2, 3, 4, 5 sont 1, 2, 1, 4 avec k × k ≤ 29, puis 29 Mod 6 = 5 et 36 > 29 : on retourne $\boxed{29}$.

3. La fonction Quoi(n, 2) retourne le plus petit diviseur de n supérieur ou égal à 2 : 5 pour 35, 7 pour 49, et n lui-même quand n n’a pas d’autre diviseur que 1 et n (29, 2). Ce plus petit diviseur est toujours un nombre premier.

4. Idée : un diviseur « petit » existe toujours quand n n’est pas premier. Si n = a × b avec 2 ≤ a ≤ b, alors a × a ≤ a × b = n. Quand k × k > n, toutes les valeurs de 2 à k ont déjà été essayées sans trouver de diviseur ; or un diviseur a ≥ 2 tel que a × a ≤ n vérifierait a × a < k × k, donc a < k, et il aurait déjà été trouvé : n n’a pas d’autre diviseur que 1 et n, et le plus petit à partir de 2 est n.

5. Idée : n est premier exactement quand son plus petit diviseur à partir de 2 est n.

Fonction Premier (n : Entier) : Booléen
DEBUT
  Retourner Quoi(n, 2) = n
FIN

Premier(29) retourne Vrai, Premier(35) retourne Faux (5 ≠ 35), Premier(2) retourne Vrai. La condition n ≥ 2 est indispensable : Quoi(1, 2) retourne 1 (1 Mod 2 = 1 et 4 > 1), si bien que Premier(1) vaudrait Vrai à tort.

1. Idée : le seul objet utilisé sans jamais être affecté est ch, manipulé par Long, par ses rangs et par Sous_chaine ; les retours sont 0 ou 10 × (un entier) + Valeur(c).

Fonction Inconnu (ch : Chaîne) : Entier

2. Tableau de déclaration des objets locaux :

3. Idée : chaque appel retire le dernier caractère ; la multiplication par 10 ne peut se faire qu’au retour de l’appel suivant.

On retourne $\boxed{2026}$.

4. La fonction Inconnu retourne l’entier formé par les chiffres de ch, pris dans leur ordre, les autres caractères étant ignorés : chaque appel place le dernier chiffre en unités après avoir multiplié par 10 le nombre formé par les chiffres qui le précèdent.

5. Inconnu("Bac") retourne 0 : aucun caractère n’est un chiffre, tous les appels retournent Inconnu(s) jusqu’à la chaîne vide. Inconnu("x07") retourne 7 : en remontant, "" et "x" donnent 0, "x0" donne 10 × 0 + 0 = 0, puis "x07" donne 10 × 0 + 7 = 7. Le résultat ne distingue donc pas une chaîne sans chiffre d’une chaîne dont les chiffres sont des zéros, et les zéros de tête sont perdus.