Aller au contenu

TNSI: Exercices sur la Récursivité⚓︎


Nombres⚓︎

🚀

Écrire une fonction récursive f(n:int)->int qui accepte en argument un entier \(n\) et qui renvoie l'entier qui est le produit: \(1\times 2\times 3\times ...\times n\) c'est à dire le produit de tous les nombres entiers inférieurs ou égaux à \(n\) (jusqu'à/en commençant par \(1\))

fonctions Pair() et Impair() 🚀

    • vrai si \(n\) est pair
    • faux si \(n\) est impair

    Écrire une fonction récursive pair(n:int)->bool qui renvoie :

    Corr 
    1
2
3
4
5
6
7
    def pair(n:int)->bool:
    if n == 0: # (1)
        return True
    elif n == 1: # (2)
        return False
    else: # (3)
        return pair(n-2)
    1. 1er cas de base
    2. 2ème cas de base
    3. Appel Récursif

  2. Écrire une fonction récursive impair(n:int)->bool qui renvoie :

    • vrai si \(n\) est impair
    • faux si \(n\) est pair
    Corr 
    1
2
3
4
5
6
7
    def impair(n:int)->bool:
    if n == 0: # (1)
        return False
    elif n == 1: # (2)
        return True
    else: # (3)
        return impair(n-2)
    1. 1er cas de base
    2. 2ème cas de base
    3. Appel Récursif

fonctions pair() et impair() imbriquées 🚀🚀

Écrire deux fonctions récursives imbriquées, pair(n:int)->bool et impair(n:int)->bool de sorte qu'elles soient définies l'une par rapport à l'autre de manière récursive:

  • pair(n) est vrai si impair(n-1) est vrai
  • Et réciproquement : impair(n) est vrai si pair(n-1) est vrai
  • pair(0) est vrai
  • impair(1) est vrai
Corr 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def pair(n:int)->bool:
    if n == 0: # (1)
        return True
    elif n == 1: # (2)
        return False
    else:  # (3)
        return impair(n-1)

def impair(n:int)->bool:
    if n == 0: # (4)
        return False
    elif n == 1: # (5)
        return True
    else: # (6)
        return pair(n-1)

nbPair = 6
nbImpair = 7
print(f"{nbPair} pair ? {pair(nbPair)}")
print(f"{nbImpair} pair ? {impair(nbImpair)}")
  1. 1er cas de base de la fonction pair
  2. 2ème cas de base de la fonction pair
  3. La fonction pair (d'argument n) appelle récursivement la fonction impair (d'argument n-1)
  4. 1er cas de base de la fonction impair
  5. 2ème cas de base de la fonction impair
  6. La fonction impair (d'argument n) appelle récursivement la fonction pair (d'argument n-1)

Nombres Romains 🚀🚀

La page wikipedia suivante résume ce qu'il faut savoir sur la numération romaine (wikipedia)

  1. Romain \(\Rightarrow\) Indien On se donne le dictionnaire suivant:
ROMAIN = { 'M' : 1000, 
          'D' : 500,
          'C' : 100, 
          'L' : 50, 
          'X' : 10, 
          'V' : 5, 
          'I' : 1}

Écrire une fonction récursive romain_vers_indien(s:str)->int qui prend en paramètre une chaîne de caractères s représentant un nombre romain sous forme de chaîne, et dont le résultat est l’entier correspondant écrit dans la notation décimale positionnelle usuelle, dite écriture indienne.

Ex: Pour s="MMXXI", romain_vers_indien('MMXXI') renvoie 2021

Corr 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
ROMAIN = { 'M' : 1000, 
            'D' : 500,
            'C' : 100, 
            'L' : 50, 
            'X' : 10, 
            'V' : 5, 
            'I' : 1
            }

def romain_vers_indien(s:str)->int:
    if len(s) == 0:
        return 0
    elif len(s) == 1: # il ne reste plus qu'un seul caractère
        return ROMAIN[s[0]]
    elif len(s) >= 2:
        if s[0:2] == "IV":
        return 4 + romain_vers_indien(s[2:])
        elif s[0:2] == "IX":
        return 9 + romain_vers_indien(s[2:])
        elif s[0:2] == "XL":
        return 40 + romain_vers_indien(s[2:])  
        elif s[0:2] == "XC":
        return 90 + romain_vers_indien(s[2:])  
        elif s[0:2] == "CD":
        return 400 + romain_vers_indien(s[2:])
        elif s[0:2] == "CM":
        return 900 + romain_vers_indien(s[2:])
        else:
        return ROMAIN[s[0]] + romain_vers_indien(s[1:])

s = "MCDLXXIII"
print(f"{s}={romain_vers_indien(s)}")
  1. Réciproquement Indien \(\Rightarrow\) Romain

Écrire une fonction récursive indien_vers_romain(n:int)->str qui prend en paramètre un nombre n représentant un nombre entier sous forme indienne, et qui renvoie en sortie la chaîne de caractères représentant son écriture en nombre romains.

Ex: Pour n=2021, indien_vers_romain(2021) renvoie MMXXI

Corr 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
ROMAIN = { 'M' : 1000, 
            'D' : 500,
            'C' : 100, 
            'L' : 50, 
            'X' : 10, 
            'V' : 5, 
            'I' : 1
            }

def indien_vers_romain(n:int)->str:
    if n == 0:
        return ""
    elif n >= 1000:
        return (n//1000)*"M" + indien_vers_romain(n-(n//1000)*1000)
    elif 500 <= n <1000:
        return "D" + indien_vers_romain(n-500)
    elif 100 <= n < 500:
        if 400 <= n <500:
        return "CD" + indien_vers_romain(n-400)
        else: # 100< n < 400
        return (n//100)*"C" + indien_vers_romain(n-(n//100)*100)
    elif 50 <= n < 100:
        if 90 <= n < 100:
        return "XC"+indien_vers_romain(n-90)
        else: # 50 <= n <= 89
        return "L"+indien_vers_romain(n-50)
    elif 10 <= n < 50:
        if 40 <= n < 50:
        return "XL"+indien_vers_romain(n-40)
        else: # 10 <= n < 40
        return (n//10)*"X" + indien_vers_romain(n-(n//10)*10)
    else: # 1<= n < 10
        if n == 9:
        return "IX"+indien_vers_romain(n-9)
        elif 5 <= n < 9:
        return "V"+indien_vers_romain(n-5)
        elif n == 4:
        return "IV"+indien_vers_romain(n-4)
        else: # 1 <= n < 4
        return n*"I"

n = 1729
print(f"{n}={indien_vers_romain(n)}")

Représentation Binaire Récursive 🚀🚀🚀

  1. Écrire une fonction récursive dec2bin(n:int)->list qui renvoie la représentation binaire d’un nombre n sous forme d'une liste.
    Par ex: dec2bin(5) renvoie [1,0,1]
  2. Écrire la "même" fonction récursive, mais qui renvoie une chaîne de caractère (au lieu d'une liste).
    Par ex: dec2bin(5) renvoie '101'
  3. Écrire une fonction récursive bin2dec(l:list)->int qui accepte en entrée une liste l représentant le nombre binaire, et qui renvoie en sortie l'entier correspondant à conversion de l en nombre décimal.
    Par ex: bin2dec([1,0,1]) renvoie la chaîne 5
  4. Écrire une fonction récursive hexa2bin(list)->list qui renvoie la représenation binaire d'un nombre hexadécimal (donné sous forme de str), sous forme de liste.
    Par ex: hexa2bin(['A','3','F']) renvoie [1,0,1,0,0,0,1,1,1,1,1,1]
  5. Écrire une fonction récursive bin2hexa(l:list)->list qui accepte en entrée une liste l représentant le nombre binaire, et qui renvoie en sorte l'écriture en hexadécimal (de l) sous forme d'une liste, correspondant à conversion de l en nombre décimal.
    Par ex: bin2hexa([1,0,1,1,0,1,1,0,1,1]) renvoie ['2','D','B']

🚀

Transformer la fonction itérative somme suivante en une fonction récursive:

def somme(l:list)->float:
  s = 0
  for valeur in l:
      s += valeur
  return s

🚀

Que fait l'algorithme récursif suivant? donné en pseudo-code ..

fonction f(n):
  SI n=1 ALORS
      renvoie 0
  SINON
      renvoie 1+f(n//2)
  FINSI

🚀

Que fait l'algorithme récursif suivant? donné en pseudo-code ..

fonction f(n):
  SI n=0 ALORS
      renvoie f(n//2)
  SINON
    renvoie n%2

🚀🚀🚀

Dans cet exercice, on suppose connu, et on pourra utiliser, le principe de la recherche dichotomique d'un nombre 1. Par compréhension de liste, créer un tableau T (une liste Python) contenant 10 nombres entiers aléatoires entre 1 et 50
2. Écrire une fonction récursive maxi(T:list)->int qui détermine le maximum d'un Tableau T (une liste Python) de nombres entiers.
3. Écrire une fonction récursive mini(T:list)->int qui détermine le maximum d'un Tableau T (une liste Python) de nombres entiers.

Chaînes de caractères⚓︎

🚀

Soit s une chaine de caractères, écrire un algorithme récursif permettant de déterminer sa longueur.

🚀

Soit phrase une chaîne de caractère. Proposer une fonction récursive inverse(phrase:str)->str qui accepte en entrée une chaîne phrase en argument, et qui renvoie en sortie une chaîne inversée. Exemple : allo devient olla

🚀

On appelle permutation d’une chaîne de caractères s toute chaîne de même longueur que s contenant les mêmes caractères que s. Par exemple, la chaîne 'eadbc' est une permutation de la chaîne 'abcde'.

Écrire une fonction récursive qui construit la liste de toutes les permutations possibles d’une chaîne s

NB il sera probablement nécessaire de définir des fonctions auxiliaires, on essaiera de les coder récursivement aussi.

Des Tours Empilées 🚀🚀🚀

On dispose de \(n\) disques de couleurs, de diamètres distincts, et de 3 tours notées \(A\), \(B\) et \(C\).

Position Initiale Tous les disques sont sur la tour A (gauche), dans l'ordre décroissant (le plus grand disque en bas)
Position Finale : But à Atteindre
Tous les disques doivent être placés sur la Tour C, dans l'ordre décroissant
RÈGLES DU JEU

  • On ne peut déplacer qu'un seul disque à la fois (d'une tour vers une autre)
  • On NE PEUT PAS déposer un disque plus grand sur un disque plus petit.

Travail à Faire
1. Proposer un algorithme, qui demande en entrée le nombre \(n\) de disques à déplacer de "A" vers "C", et une fonction récursive résolvant le problème des Tours Empilées, c'est-à-dire qui détaille chacun des déplacements entre les tours (du disque supérieur de chaque tour), pour parvenir jusqu'à la Position Finale. Exemple de Syntaxe attendue: 

A --> C
A --> B
C --> B
etc...

Questions Diverses

Que dire de ces sigles ?

  • VISA : VISA International Service Association
  • GNU : GNU is Not Unix
  • WINE : Wine Is Not an Emulator