Exercices récursivité

Analyse d’une fonction récursive

Soit le programme Python suivant :

Quel est le résultat affiché par ce programme?
Quel est le cas de base dans cette fonction récursive ?
Qu’est ce qui garantit dans les appels récursifs 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 .

 

 

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] .
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.

 

 

Figures récursives

On peut décrire la figure suivante de façon récursive :

La figure est formée d’un cercle et de deux copies de ce cercle ayant subies une réduction d’un facteur 2, ces deux petits cercles étant tangents extérieurement au cercle initial et tels que les lignes des centres sont parallèles aux axes du repère. Ces deux petits cercles deviennent à leur tour “cercle initial” pour poursuivre la figure.

On peut traduire avec python ce descriptif récursif de la façon suivante :

Qu’est ce qui garantit que cette fonction ne s’appellera qu’un nombre fini de fois ?
Dans l’appel initial, si l’on change CerclesRec(0, 0, 8)  par CerclesRec(0, 0, 64), qu’obtiendra-t-on ?
Modifier le programme python précédent pour obtenir la figure suivante :

On pourra utiliser un paramètre supplémentaire pour définir la fonction récursive (abscisse du centre, ordonnée du centre, rayon du cercle, position du voisin) où position sera l’une des chaînes de caractères : haut, bas, droite, gauche.

 

pylab.Rectangle((x,y),a,b, fill =False)  permet de définir un rectangle dont les côtés, de longueurs a  et b , sont parallèles aux axes et dont le sommet “sud-ouest” a pour coordonnées (x,y) .

Écrire un programme récursif pour la figure dont on donne deux étapes ci-dessous :

 

pylab.Polygon([(xa,ya),(xb,yb),(xc,yc)], fill =False)  permet de définir un triangle dont les sommets ont pour coordonnées (xa,y a) , (xb,yb) , (xc,yc) .

Écrire un programme récursif python pour la figure dont on donne deux étapes ci-dessous :

 

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 de manière récursive :

\(C(n, p) = \begin{cases}
1, & \text{si $n=0$ ou $p=0$} \\
C(n-1, p-1)+C(n-1, p), & \text{sinon}
\end{cases}\)
Écrire une fonction récursive C(n, p)  qui renvoie la valeur de \(C(n, p)\).
Écrire une fonction récursive qui permet de dessiner le triangle de Pascal

 

 

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)\)
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 de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code