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() 🚀

  1. Écrire une fonction récursive pair(n:int)->bool qui renvoie :
    • vrai si \(n\) est pair
    • faux si \(n\) est impair
  2. Écrire une fonction récursive impair(n:int)->bool qui renvoie :
    • vrai si \(n\) est impair
    • faux si \(n\) est pair

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

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

  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

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 minimum 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