RETOUR au cours sur la recursivité
Ex 1: Fonction impair
La fonction récursive impair accepte un paramètre, N, entier positif. A chaque appel récursif, la fonction s’appelle elle-même avec l’argument N-2.
La condition de base est que N == 1 au bout d’un certain nombre d’appels.
Completez le script de cette fonction.
Ex 2: Suite de Fibonacci
On définit la suite (fn) des nombres de Fibonacci par : $$\left\{\begin{matrix}\begin{align}f_0 & =0\\f_1 & =1\\f_{n+1} & =f_{n}+f_{n-1}, \forall n \in \mathbb{N}^+\end{align}\end{matrix}\right.$$
def fibo(n):
"""
algo recursif
"""
if (n==0) : return 0
if (n==1) : return 1
return fibo() + fibo()
- Compléter la dernière ligne de la fonction
fibo
avec les bons arguments - Ajouter quelques lignes au script pour afficher tous les nombres de la suite de Fibonacci, du rang 0 au rang n=10.
Ex 3: Les tours de Hanoï
Le problème des tours de Hanoi est présenté en détails dans le cours sur la recursivité ici
- Dans l’editeur plus bas: Executer le script. Puis aller dans la console et tester l’exemple proposé dans le prototypage de la fonction.
- Tester egalement avec 4 disques. Noter chaque fois le nombre de deplacements effectués.
3. Proposez une loi de recurence entre le nombre de déplacements T(N) pour N disques, et le nombre de déplacements T(N-1) pour N-1 disques.
Aide: on pourra consulter la page accromath.
Ex 4: Nombre d’occurences dans une chaine de caractères
il s’agit d’écrire une fonction recursive nombre_r(lettre, phrase) qui renvoit le nombre de fois où la lettre apparaît dans la phrase.
-
Dans le cas de base: on retourne 0 si la phrase est vide
""
. -
Pour l’heredité: On réduit la phrase en eliminant le premier caractère après chaque appel recursif: on met comme argument
phrase[1:]
à la place du paramètrephrase
.-
Si le caractère
phrase[0]
est identique àlettre
: on applique la formule de recurence suivante: $u_n = 1 + u_{n-1}$ que l’on adapte ici en:return 1 + nombre_r(lettre,phrase[1:])
-
sinon, on adapte la formule de recurence : $u_n = u_{n-1}$
-
Compléter le script et testez votre fonction avec, par exemple les arguments:
u
etlustucru
.
Ex 5: Retournement d’une liste
La fonction suivante realise un retournement d’une chaine de caractères:
def reverse_iterative(seq):
"""
Return the reverse of a string
use insert(index, elem) -- inserts the element at the given index, shifting elements to the right.
Example:
>>> reverse_iterative('abcd')
dcba
"""
reversed_seq = []
for i in range(len(seq)):
reversed_seq.insert(0, seq[i])
return reversed_seq
On peut tester cette fonction dans l’editeur ci-dessous :
seq = 'abcd'
reverse_iterative(seq)
# affiche
# ['d', 'c', 'b', 'a']
Aide pour l’écriture de l’algorithme récursif :
- le paramètre est la chaine s
- pour un caractère au rang
i
, on le permute avec le caractère au rang b: b prend la valeur de l’indexlen(s) - i - 1
, c’est à dire le symétrique de la position i dans la chaine.
Par exemple, i = 0 => a est l’index du premier caractère et b celui du dernier caractère.
La condition de base: On traite le retournement des caractères aux extremités d’une chaine dont la taille diminue au fur et à mesure des appels recursifs.
-
si la longueur de chaine est un nombre impair: Au moment où la longueur de chaine est égale à 1: Le dernier caractère non retourné est au milieu de la chaine. On renvoie ce dernier caractère:
return s
-
si la longueur de chaine est un nombre pair: Au moment où la longueur de chaine est nulle, on termine l’execution de la fonction en renvoyant
s
qui vaut''
.
dans tous les cas, on pourra exprimer cette condition de base avec:
if len(s) <= 1:
return s
La deuxième étape (la partie heredité) consiste à appeler de manière récursive la fonction après avoir permuté les caractères aux extremités: return s[m] + milieu + s[0]
Le milieu est constitué de la chaine retournée par l’appel recursif de la fonction avec pour paramètre le mot privé de ses 2 extremités.
Dans l’editeur ci-dessous:
- Tester dans la console l’exemple proposé : `reverse_iterative(‘abcd’)
- Compléter le script de la fonction
reverse_recur
RETOUR au cours sur la recursivité
Ressources
- L’editeur en ligne est proposé par https://fr.vittascience.com/python/