Fonctions récursives

Nous allons aborder les fonctions récursives en Python, c'est à dire les fonction dont le calcul nécessite d'invoquer la fonction elle-même. Les exercices proposés se feront naturellement autour de la notion de suite définie par récurrence.

ISuites définies par récurrence

Prenons l'exemple de la factorielle $u_n=n !$. Elle peut être définie par la relation de récurrence : $$ \left\{ \begin{array}{ccc} u_{n+1} &=& (n+1)\times u_n \\ u_0&=& 1 \end{array} \right. $$ Ce qui donne l'implémentation suivante en Python :

def factorielle(n):
    if n==0:
        return 1
    else:
        return (n+1)*factorielle(n-1)

Créer un fichier suites.py.

Les suites suivantes sont définies par récurrence et convergent toutes les deux vers le nombre d'or $\Phi$ : $$ \left\{ \begin{array}{ccc} u_{n+1} &=& \sqrt{1+u_n} \\ u_0&=& 0 \end{array} \right. $$ $$ \left\{ \begin{array}{ccc} v_{n+1} &=& 1+\frac{1}{1+u_n} \\ v_0&=& 0 \end{array} \right. $$ Définir deux fonctions récursives U() et V() qui implémentent les deux suites.
Définir une fonction seuil(s, u, l) prenant en argument un flottant $s$ (le seuil), une suite $u$ (sous forme d'une fonction), un flottant $l$ (la limite de la suite) et qui renvoie le premier entier $N$ tel que : $$ |u_n - l| \lt s $$ Attention, si la suite et la limite données ne correpondent pas, la fonction seuil() peut ne pas s'arrêter.
Définir une fonction seuils(u, l, N) prenant en argument une suite $u$ (sous forme de fonction), un flottant $l$ (la limite de la suite), un entier $N$ et qui renvoie la liste des résultats renvoyés par la fonction seuil(s, u, l) pour $s \in \{10^{-1}, 10^{-2}, ..., 10^{-N} \}$.
En combien d'itérations la suite $(u_n)$ converge t'elle vers $\Phi$ ?
En combien d'itérations la suite $(v_n)$ converge t'elle vers $\sqrt{2}$ ?

Indices

Replier

La fonction U() nécessite le module math pour utiliser la racine carrée sqrt()
La valeur absolue est calculée par la fonction abs() . Il faut utiliser une boucle while . La suite doit donc impérativement converger vers la limite donnée. Un nombre maximum d'itération peut être posé pour éviter les boucles infinies.
Astuce Python : list(map(lambda x:10**(-x), range(1,N))) (bon, c'est du python avancé et on peut faire autrement, mais on y reviendra plus tard... ce langage a des variantes très concises)

Dans le fichier suites.py, créer la fonction récursive fibo(u0, u1, n) qui à partir des deux termes de départ calcule le $n$-ième suivant la relation de récurrence suivant : $$ \left\{ \begin{array}{ccc} F_{n+2} &=& F_{n+1} + F_{n} \\ F_0&=& 0 \\ F_1&=& 1 \\ \end{array} \right. $$

Indices

Replier

IIHanoï

Le problème des tours de Hanoï est le suivant : on dispose de trois "tours" A, B et C formées d'un empilement de disques. Les disque peuvent être déplacés d'une tour vers une autre si ils respectent la règle suivante : à tout moment, chaque disque repose sur un disque plus grand.

Au départ, tous les disques sont sur le tas A. Le but est de tous les mettre sur le tas C en respectant la règle. Pour $n=4$ disques, la solution est la suivante :

Créer un fichier hanoi.py qui contiendra une fonction capable de résoudre le problème pour $n$ disque.

Créer une fonction récursive hanoi(n, a, b, c) prenant en arguments n un entier représentant le nombre de disques, a un caractère (par exemple 'A') représentant la tour de départ, b un caractère représentant la tour intermédiaire, et c un caractère représentant la tour finale (celle où doivent reposer les disques à la fin).
À l'aide de print() Cette fonction devra décrire par des phrases les étapes à réaliser comme "Déplacer A sur B"

Indices

Replier

L'idée est de mettre en évidence l'aspect récursif de la solution. Pour déplacer $n$ disques de A vers C, je fais "deux" étape : j'en déplace $n-1$ de A vers B, je déplace la plus grande restée seule en A vers B, puis je déplace les $n-1$ de B vers C.

Pour aller plus loin, le programme peut être amélioré de la manière suivante :

Utiliser une variable globale pour compter le nombre d'étapes, et l'afficher à la fin.
Afficher en un seul message plusieurs messages identiques à la suite. Par exemple : "Déplacer A sur B 50 fois"

Indices

Replier

Pour compter les messages consécutifs identiques, on pourra utiliser une variable globale etape_precedente et un compteur N_identiques . Si un déplacement en cours est identique à celui contenu dans etape_precedente , incrémente N_identiques et sinon on affiche le message et on remet N_identiques à 0.