exercices sur la recursivité

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()
  1. Compléter la dernière ligne de la fonction fibo avec les bons arguments
  2. 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

  1. Dans l’editeur plus bas: Executer le script. Puis aller dans la console et tester l’exemple proposé dans le prototypage de la fonction.
  2. 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.

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ètre phrase.

    • Si le caractère phrase[0] est identique à lettre: on applique la formule de recurence suivante: un = 1 + un-1 que l’on adapte ici en: return 1 + nombre_r(lettre,phrase[1:]

    • sinon, on adapte la formule de recurence : un = un-1

Compléter le script et testez votre fonction avec, par exemple les arguments: u et lustucru.

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 une cellule d’un jupyter notebook :

<tr>
    <th scope="row">OUT</th>
    <td>
     ['d', 'c', 'b', 'a']
    </td>
</tr>

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’index len(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:

  1. Tester dans la console l’exemple proposé : `reverse_iterative(‘abcd’)
  2. Compléter le script de la fonction reverse_recur

RETOUR au cours sur la recursivité

Ressources