Construction récursive de chaine de caractères⚓︎

D'après 2022, Polynésie, J1, Ex. 1

On rappelle qu'une chaine de caractères peut être représentée en Python par un texte entre guillemets "" et que :

la fonction len renvoie la longueur de la chaine de caractères passée en paramètre ;
si une variable ch désigne une chaine de caractères, alors ch[0] renvoie son premier caractère, ch[1] le deuxième, etc ;
l'opérateur + permet de concaténer deux chaines de caractères.

Exemples

🐍 Console Python

>>> texte = "bricot"
>>> len(texte)
6
>>> texte[0]
"b"
>>> texte[1]
"r"
>>> "a" + texte
"abricot"

On s'intéresse dans cet exercice à la construction de chaines de caractères suivant certaines règles de construction.

Règle A

Une chaine est construite suivant la règle A dans les deux cas suivants :

soit elle est égale à "a" ;
soit elle est de la forme "a" + chaine + "a", où chaine est une chaine de caractères construite suivant la règle A.

Règle B

Une chaine est construite suivant la règle B dans les deux cas suivants :

soit elle est de la forme "b" + chaine + "b", où chaine est une chaine de caractères construite suivant la règle A ;
soit elle est de la forme "b" + chaine + "b", où chaine est une chaine de caractères construite suivant la règle B.

Fonction choice du module random

On a reproduit ci-dessous l'aide de la fonction choice du module random.

🐍 Console Python

>>> from random import choice
>>> help(choice)
Help on method choice in module random:
choice(seq) method of random.Random instance
Choose a random element from a non-empty sequence.

choice(seq) renvoie un élément de seq (qui peut être une liste) de façon pseudo-aléatoire.

La fonction A ci-dessous renvoie une chaine de caractères construite suivant la règle A, en choisissant aléatoirement entre les deux cas de figure de cette règle.

🐍 Script Python

def A():
    if choice([True, False]):
        return "a"
    else:
        return "a" + A() + "a"

1.a. Cette fonction est-elle récursive ? Justifier.

Réponse

La fonction A s'appelle elle-même, donc A est une fonction récursive.

1.b. La fonction choice([True, False]) peut renvoyer False un très grand nombre de fois consécutives. Expliquer pourquoi ce cas de figure amènerait à une erreur d'exécution.

Réponse

Si choice([True, False]) renvoie False consécutivement un nombre de fois supérieur à la limite de profondeur de récursion autorisée (1000 par défaut avec Python), dans ce cas une erreur d'exécution se produit.

Pour aller plus loin

On pourrait modifier cette limite à \(10^6\) avec le code suivant

🐍 Script Python

import sys
sys.setrecursionlimit(10**6)

Dans la suite, on considère une deuxième version de la fonction A. À présent, la fonction prend en paramètre un entier n tel que,

si la valeur de n est négative ou nulle, la fonction renvoie "a" ;
si la valeur de n est strictement positive, elle renvoie une chaine de caractères construite suivant la règle A avec un n décrémenté de 1, en choisissant aléatoirement entre les deux cas de figure de cette règle.

🐍 Script Python

def A(n):
    if ... or choice([True, False]) :
        return "a"
    else:
        return "a" + ... + "a"

2.a. Recopier sur la copie et compléter aux emplacements des points de suspension ... le code de cette nouvelle fonction A.

Réponse

🐍 Script Python

def A(n):
    if (n <= 0) or choice([True, False]) :
        return "a"
    else:
        return "a" + A(n - 1) + "a"

2.b. Justifier le fait qu'un appel de la forme A(n) avec n un nombre entier positif inférieur à 50, termine toujours.

Réponse

Pour \(n > 0\), l'appel à A(n) provoque ou bien un arrêt de la fonction, ou bien un appel récursif avec le paramètre n - 1.

Un appel à A(50) pourrait provoquer dans le pire des cas 50 appels récursifs pour arriver à A(0) qui termine, ou alors terminer avant !

On donne ci-après le code de la fonction récursive B qui prend en paramètre un entier n et qui renvoie une chaine de caractères construite suivant la règle B.

🐍 Script Python

def B(n):
    if (n <= 0) or choice([True, False]):
        return "b" + A(n - 1) + "b"
    else:
        return "b" + B(n - 1) + "b"

On admet que :

les appels A(-1) et A(0) renvoient la chaine "a" ;
l'appel A(1) renvoie la chaine "a" ou la chaine "aaa" ;
l'appel A(2) renvoie la chaine "a", la chaine "aaa" ou la chaine "aaaaa".

3. Donner toutes les chaines possibles renvoyées par les appels B(0), B(1) et B(2).

Réponse

B(0) renvoie "bab"
B(1) renvoie "bab" ou "bbabb".
B(2) renvoie "bab", "baaab", "bbabb" ou "bbbabbb".

On suppose maintenant qu'on dispose d'une fonction raccourcir qui prend comme paramètre une chaine de caractères de longueur supérieure ou égale à 2, et renvoie la chaine de caractères obtenue à partir de la chaine initiale en lui ôtant le premier et le dernier caractère.

Par exemple :

🐍 Console Python

>>> raccourcir("abricot")
"brico"
>>> raccourcir("ab")
""

4.a. Recopier sur la copie et compléter les points de suspension ... du code de la fonction regle_A ci-dessous pour qu'elle renvoie True si la chaine passée en paramètre est construite suivant la règle A, et False sinon.

🐍 Script Python

def regle_A(chaine):
    n = len(chaine)
    if n >= 2:
        return (chaine[0] == "a") and (chaine[n - 1] == "a") and regle_A(...)
    else:
        return chaine == ...

Réponse

🐍 Script Python

def regle_A(chaine):
    n = len(chaine)
    if n >= 2:
        return (chaine[0] == "a") and (chaine[n - 1] == "a") and regle_A(raccourcir(chaine))
    else:
        return chaine == "a"

4.b. Écrire le code d'une fonction regle_B, prenant en paramètre une chaine de caractères et renvoyant True si la chaine est construite suivant la règle B, et False sinon.

Réponse

🐍 Script Python

def regle_B(chaine):
    n = len(chaine)
    if n >= 2:
        return (chaine[0] == "b") and (chaine[n - 1] == "b") and (
            regle_A(raccourcir(chaine)) or regle_B(raccourcir(chaine))
        )
    else:
        return False