Exercices récursivité

par · Publié · Mis à jour

Analyse d’une fonction récursive

Soit le programme Python suivant :

def f(a, b) :
   """ a et b sont deux entiers naturels non nuls """
   if b == 1 :
      return a
   return a + f(a, b-1)

print(f(3, 5))
Déterminer, sans utiliser d’ordinateur, le résultat affiché par ce programme (utiliser un papier et un crayon !!).
Identifier le cas de base de cette fonction récursive.
Démontrer que le programme finira par s’arrêter.
Que retourne f(a, b) (a et b  étant des entiers naturels non nuls) ?

 

 

Occurrences

Réaliser une fonction nb_occurrences(s, c)  qui renvoie le nombre d’occurrences du caractère c dans la chaîne s .
Correction
def nb_occurrences(s, c):
    """ renvoie le nombre d'occurrences 
        du caractère c dans la chaîne s
    """
    if len(s)>0:
        n = nb_occurrences(s[1:], c)
        if s[0]==c:
            return n+1
        else:
            return n
    return 0

# Version plus courte :
def nb_occurrences(s, c):  
    if len(s)>0: 
        return 1*(s[0]==c) + nb_occurrences(s[1:], c) 
    else:
        return 0

 

 

Parcours d’une arborescence de fichiers

  • La fonction os.listdir(path)  (du module os ) permet d’obtenir la liste de tous les fichiers et dossier placés directement dans le dossier désigné par le chemin path.
  • La fonction os.path.isfile(path)(du module os.path ) renvoie True si le chemin path  désigne un fichier (et donc False  s’il s’agit d’un dossier)
  • La fonction os.path.splitext(path) permet de séparer l’extension du reste du chemin path , sous la forme d’une liste [racine, extension] .
  • La fonction os.path.join(path1, path2, ...) permet de concaténer des éléments de chemin sans trop se soucier de la syntaxe, qui rappelons-le, varie d’un OS à l’autre !
En utilisant ces seules fonctions, écrire une fonction liste_fichiers(path, ext) qui renvoie la liste de tous les fichiers ayant l’extension ext situés dans d’un dossier désigné par le chemin path , ainsi que dans tous ses sous-dossiers.
Correction
# Version "affichage"
def liste_fichiers(path, ext):
    """ renvoie la liste des fichiers (chemins absolus) ayant l'extension <ext>
        situés dans le dossier <path>
        et dans tous ses sous dossiers
    """
    try:
        lst_p = os.listdir(path)
    except:
        lst_p = []
    for p in lst_p:
        abs_p = os.path.join(path, p)
        if os.path.isfile(abs_p):
            if os.path.splitext(p)[1] == ext:
                print(abs_p)
        else:
            liste_fichiers(abs_p, ext)

# Version "Liste"
def liste_fichiers(path, ext): 
    """ renvoie la liste des fichiers (chemins absolus) ayant l'extension <ext> situés dans le dossier <path> et dans tous ses sous dossiers """ 
    try:
        lst_p = os.listdir(path)
    except:
        lst_p = []
    liste = []
    for p in lst_p:
        abs_p = os.path.join(path, p)
        if os.path.isfile(abs_p):
            if os.path.splitext(p)[1] == ext:
                liste.append(abs_p)
        else:
            liste += liste_fichiers(abs_p, ext)
    return liste

 

 

Triangle de Pascal

Le triangle de Pascal (Blaise Pascal !) est une présentation des coefficients binomiaux sous la forme d’un triangle :

On le définit par récurrence :

\(C(n, p) = \begin{cases}
1, & \text{si $n=p$ ou $p=0$} \\
C(n-1, p-1)+C(n-1, p), & \text{sinon}
\end{cases}\)

avec \(0\lt p \leq n\)

Dans le triangle de Pascal, \(n\) correspond à l’indice des lignes et \(p\) à celui des colonnes.

 

Écrire une fonction récursive C(n, p) qui renvoie la valeur de \(C(n, p)\).
Correction
def C(n,p) :
    if p == n or p == 0:
        return 1
    else :
        return C(n-1,p-1)+C(n-1,p)

Ou bien :

def C(n,p) :
    if 0 < p < n:
        return C(n-1, p)+C(n-1,p-1)
    return 1

 

Écrire une fonction récursive qui permet de « dessiner » le triangle de Pascal.

 

Conversion Décimal ->Binaire

Écrire une fonction récursive binaire(n) qui renvoie la représentation binaire naturel d’un nombre n (sous forme de chaîne de caractères : "0" ou "1").

 

 

Permutations

Écrire une fonction permutation() , sous forme récursive, permettant d’obtenir l’ensemble des permutations possibles d’un n-uplet \((e_0, e_1, \ldots, e_n)\)

Exemple : permutation([1,2,3]) doit retourner [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

 

Calculer l’ordre de complexité de cet algorithme.

 

 

Sources :

http://math.univ-lyon1.fr/irem/IMG/pdf/recurs.pdf

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *